【Floyd最短路】第七届福建省赛 FZU Problem 2271 X

http://acm.fzu.edu.cn/problem.php?pid=2271

【题意】

给定一个n个点和m条边的无向连通图，问最多可以删去多少条边，使得每两个点之间的距离（最短路长度）不变。

【思路】

首先对于多重边可以只保留最短的边，剩下的都删去
跑一次Floyd，用vis数组记录哪些边可以被松弛（注意map[i][k]+map[k][j]==map[i][j]时,i-j这条边如果在原图，也可以被删去）
最后遍历一下所有的原图的边，可以被松弛的就可以被删去

【Accepted】

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 using namespace std;
 9 
10 int n,m;
11 const int maxn=1e2+2;
12 const int maxm=4e4+2;
13 const int inf=0x3f3f3f3f; 
14 bool vis[maxn][maxn];
15 int map[maxn][maxn];
16 int mp[maxn][maxn];
17 
18 void Floyd()
19 {
20     for(int k=1;k<=n;k++)
21     {
22         for(int i=1;i<=n;i++)
23         {
24             for(int j=1;j<=n;j++)
25             {
26                 if(i==j)
27                 {
28                     continue;
29                 }
30                 if(map[i][k]<inf&&map[k][j]<inf&&map[i][k]+map[k][j]<=map[i][j])
31                 {
32                     map[j][i]=map[i][j]=map[i][k]+map[k][j];
33                     //说明这条边可以被别代替而不影响最短路，那么如果这条边是原来存在的一条边，我们就可以删去 它 
34                     vis[j][i]=vis[i][j]=true;
35                 }
36             }
37         }
38     }
39 }
40 int main()
41 {
42     int T;
43     scanf("%d",&T);
44     int cas=0;
45     while(T--)
46     {
47         memset(vis,false,sizeof(vis));
48         memset(map,inf,sizeof(map));
49         scanf("%d%d",&n,&m);
50         int ans=0;
51         for(int i=1;i<=m;i++)
52         {
53             int u,v,c;
54             scanf("%d%d%d",&u,&v,&c);
55             if(map[u][v]<inf)
56             {
57                 ans++;
58             }
59             map[u][v]=map[v][u]=min(map[u][v],c);
60         }
61         memcpy(mp,map,sizeof(mp));
62         Floyd();
63         for(int i=1;i<=n;i++)
64         {
65             for(int k=i+1;k<=n;k++)
66             { 
67                 if(mp[i][k]<inf&&vis[i][k])
68                 {
69                     ans++;
70                 }
71             }
72         }
73         printf("Case %d: %d
",++cas,ans);
74     }
75     return 0;
76 }

Floyd