题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4034
思路：要对floyd有深刻的理解才能A这道题，边数最多的情况是每两点之间都有最短的直边相连，故最多为n*(n-1)，在每两点都有最短直边相连情况下，我们可以一一删去多余的边，最后就是最终结果。即若dist[i][j]=dist[i][k]+dist[k][j],则i 与 j的这条边可以删去.若dist[i][j]>dist[i][k]+dist[k][j]，则说明dist[i][j]并不是最短路，存在矛盾，此时则不存在这样的图，输出impossible。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define MAXN 111 7 int n; 8 int dist[MAXN][MAXN]; 9 10 int main(){ 11 int _case,t=1; 12 scanf("%d",&_case); 13 while(_case--){ 14 scanf("%d",&n); 15 for(int i=1;i<=n;i++) 16 for(int j=1;j<=n;j++) 17 scanf("%d",&dist[i][j]); 18 bool flag=true; 19 int ans=0; 20 for(int k=1;k<=n&&flag;k++) 21 for(int i=1;i<=n&&flag;i++) 22 for(int j=1;j<=n&&flag;j++)if(i!=j&&j!=k&&i!=k) 23 if(dist[i][j]>dist[i][k]+dist[k][j])flag=false; 24 25 if(!flag){ printf("Case %d: impossible\n",t++);continue; } 26 for(int i=1;i<=n;i++){ 27 for(int j=1;j<=n;j++)if(i!=j){ 28 flag=true; 29 for(int k=1;k<=n;k++)if(i!=k&&j!=k){ 30 if(dist[i][j]==dist[i][k]+dist[k][j])flag=false; 31 } 32 if(flag)ans++; 33 } 34 } 35 printf("Case %d: %d\n",t++,ans); 36 } 37 return 0; 38 }