HDU 4034 Graph(Floyd变形)
http://acm.hdu.edu.cn/showproblem.php?pid=4034
题意:给你一个N个节点的有向图的最短距离矩阵,现在要你求出该有向图的最少可能的边数是多少?如果该图存在矛盾,则输出”impossible”.
分析:
对于一个有向图,最多可能有n*(n-1)条边.我们只要枚举这n*(n-1)条边,然后看看这条边是否必须存在即可.
假设我们现在考虑边i->j,看看它是否必须存在.首先我们必须假定边i->j的长度.由于我们知道i到j的最短距离,所以我们只能假定i->j边长==其最短距离.(想想为什么,更短的话,出现矛盾.更长的话,直接没有存在的必要)
如果存在d[i][k]+d[k][j]==d[i][j],那么说明i->j的边长可以由别的边生成,所以i->j的边没有存在的必要.
如果存在d[i][k]+d[k][j]<d[i][j], 那么有矛盾,直接输出impossible.
上面两种情况都不存在,说明没有任何其他边的最短距离能生成i到j的最短距离,那么i只能通过一条直边到达j来产生最短距离.
AC代码:
#include<cstdio>
using namespace std;
const int maxn = 100+10;
int d[maxn][maxn];
int main()
{
int n,T; scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
printf("Case %d: ",kase);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&d[i][j]);
bool flag = true;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)//检测每条边
for(int k=1;k<=n;k++)if(i!=j&&j!=k&&i!=k)
if(d[i][j]> d[i][k]+d[k][j]) flag=false;
if(!flag) { printf("impossible\n"); continue; }
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(i!=j)//检测每条边
{
bool flag=true;
for(int k=1;k<=n;k++)if(j!=k&&i!=k)
if(d[i][j] == d[i][k]+d[k][j])
flag=false;
if(flag) ++ans;
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码