4034 Graph

it2022-05-06  10

题目大概意思:给定一个图,任意俩点间的最短路已知,判断该图是否存在,若不存在,则输出impossible,存在,输出可能的最少边数

分析:

首先,判断该图是否存在,这个很容易,对已给的图求出任意点的最短路,若存在俩点最短路与原图不同(即所给图存在更短路),则不存在;

若该图存在,求出最少的边数,其实就是一个删边的过程,起始的边数是n*(n-1),若俩点之间存在其他路径长等于直接相连时的路径长,则删去,注意,要判断是否重复删边(orz,这里WA了几次);

求任意俩点之间的最短路,用floyd算法,复杂度O(n^3),因为n最大为100,无压力~~

View Code #include<iostream>using namespace std;int map[101][101],g[101][101],n;bool mat[101][101];int main(){int cas,T=0; scanf("%d",&cas);while(cas--) { scanf("%d",&n);int count=n*(n-1);for(int i=0;i<n;i++)for(int j=0;j<n;j++) { scanf("%d",&map[i][j]); g[i][j]=map[i][j]; } memset(mat,0,sizeof(mat));for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++) { if(i==j)continue;if(map[i][k]&&map[k][j]&&g[i][j]>=g[i][k]+g[k][j]) {if(g[i][j]==g[i][k]+g[k][j]&&!mat[i][j]) { mat[i][j]=1;//记录是否删过 count--; } g[i][j]=g[i][k]+g[k][j]; } }int flag=0; printf("Case %d: ",++T);for(int i=0;i<n;i++) {for(int j=0;j<n;j++)if(g[i][j]&&g[i][j]!=map[i][j])//判断是否存在更短路 { flag=1;break; }if(flag)break; }if(!flag) printf("%d\n",count);else printf("impossible\n"); }return 0;}

转载于:https://www.cnblogs.com/nanke/archive/2011/09/12/2173982.html

相关资源:数据结构—成绩单生成器

最新回复(0)