福州大学2271x——弗洛伊德最短路

福州大学 Problem 2271 X

题意

N个城市，M条路，保证最开始是连通图。(N<=100)现在需要删除掉一些路，要保证删除后各个城市之间的距离不变（最短路径长度不变）尽可能得使得删除的路的条数更多。两个城市之间可能有多条路。

思路

我们是要删除一些边，保证城市间最短路长度不变。首先两个城市间若有1条以上的路，那么必定是要删除。其次，我么可以用弗洛伊德最短路算法，算得各个城市之间的最短路径长度。然后我们考虑删除，原图中两个城市间有路并且大于两个城市的最短路，那么此边必定要删除。然后，因为题目是要尽可能删除更多的边，那么当存v1与v2的一条边u，u的长度等于v1与v2的最短路径长度且u！=此最短路，那么u就要被删除，因为要尽可能多删除。

AC代码

#include<stdio.h> #include<iostream> #include<cmath> #include<cstring> #define inf 0x3f3f3f3f using namespace std; const int maxn = 110; int map[maxn][maxn]; //弗洛伊德用的图 由原图复制过来 int cost[maxn][maxn]; //原图 int vis[maxn][maxn]; int n,m; void flo() { int k,i,j; //Floyd-Warshall算法核心语句 for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) { if(i == j) continue; if(map[i][j]>=map[i][k]+map[k][j] ) { map[i][j]=map[i][k]+map[k][j]; vis[i][j] = 1; } } } int main() { int T; scanf("%d",&T); int Case = 1; while(T--) { int ans1 = 0; int ans2 = 0; memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); //初始化为inf for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cost[i][j]=inf; for(int i = 0; i < m ;i++) { int x,y,s; scanf("%d%d%d",&x,&y,&s); if(cost[x][y] != 0 && cost[x][y] != inf) { ans1 ++; //一开始就要删除的边 cost[x][y] = min(cost[x][y],s); cost[y][x] = min(cost[y][x],s); } else { cost[x][y] = s; cost[y][x] = s; } } //把cost边复制个给map，用于弗洛伊德算法。 for(int i = 1; i <= n ;i++) { for(int j = 1; j <= n ;j++) { map[i][j] = cost[i][j]; } } flo(); for(int i =1 ;i <= n ;i++) { for(int j = 1; j<= n ;j++) { //有边 if(cost[i][j] != 0 && cost[i][j] != inf ) { //大于最短路 删 if(map[i][j] < cost[i][j]) { ans2++; } //等于最短路 并且标记要删除 删 else if(map[i][j] == cost[i][j] && vis[i][j] == 1) { ans2++; } } } } int ans = ans1 + ans2 / 2; //因为是无向图所以ans2要除以2 ，会算两遍 printf("Case %d: %d\n",Case++,ans); } return 0; }