hdu 4034

比赛时才发现自己基础算法都忘得光光了，逆向floyd

i->j经过k点，只要i到j的距离大于或者等于，就把这边标记，实为去掉。。。此时整个图就减一条边

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<limits.h>
 4 #include<memory.h>
 5 using namespace std;
 6 #define INF INT_MAX
 7 #define maxn 110
 8 int n;
 9 int d[maxn][maxn],m[maxn][maxn];
10 int vis[maxn][maxn];
11 void init()
12 {
13     memset(d,INF,sizeof(d));
14     memset(vis,0,sizeof(vis));
15 }
16 void input()
17 {
18     for(int i = 0; i < n; i++)
19         for(int j = 0;  j < n; j++)
20         {
21             scanf("%d",&d[i][j]);m[i][j] = d[i][j];
22         }
23 
24 }
25 int floyd()//逆向floyd
26 {
27     int cnt = 0;
28     for(int k = 0; k < n; k++)
29         for(int i = 0; i < n; i++)
30             for(int j = 0; j < n; j++)
31                 if(i != k && k != j && d[i][j] >= d[i][k] + d[k][j])
32                 {
33                     vis[i][j] = 1;
34                     d[i][j] = d[i][k] + d[k][j];
35                     if(d[i][j] < m[i][j])return -1;
36                 }
37     for(int i = 0; i < n; i++)
38         for(int j = 0; j < n; j++)
39             if(vis[i][j]) cnt++;
40     return n * n - n - cnt;
41 }
42 int main()
43 {
44     int T;
45     scanf("%d",&T);
46     int cas = 1;
47     while(T--)
48     {
49         scanf("%d",&n);
50         init();
51         input();
52         printf("Case %d: ",cas++);
53         int t = floyd();
54         if(t == -1) puts("impossible");
55         else cout<<t<<endl;
56     }
57 }