这道题在uvalive和CF的GYM里都能找到,但是uvalive的数据好像有问题,过不了,建议去CF里的GYM里找。
题意:给你一个邻接矩阵代表最短路的情况,让你给出n条原始的边,使得这个最短路成立。
方法:要找的都是必要的边。先构造1棵最小生成树,这n-1条边是部分答案,然后是找最后一条边。这里先要通过这棵树做n遍dfs求出任意两点的距离,然后再与最短路距离比较,找到仍未满足最短距离并且这两个点的最短距离最小的边,如果都已满足最短距离则随意添加一条重边即可。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #define maxn 1<<29 using namespace std; struct edge { int from,to,len; }; vector<int>g[2005]; vector<edge>edges; vector<edge>ans; int p[2005][2005]; int a[2005][2005]; int n; int d[2005]; bool v[2005]; int pre[2005]; void dfs(int u,int fa,int cnt) { v[u]=1; a[fa][u]=cnt; int size=g[u].size(); for(int i=0;i<size;i++) { edge &e=edges[g[u][i]]; if(!v[e.to]) { dfs(e.to,fa,cnt+e.len); } } } int main() { bool fff=0; while(scanf("%d",&n)!=EOF) { if(fff)printf("\n"); else fff=1; for(int i=1;i<=n;i++) { g[i].clear(); for(int j=1;j<=n;j++) { scanf("%d",&p[i][j]); } } edges.clear(); ans.clear(); for(int i=2;i<=n;i++) { d[i]=p[1][i]; pre[i]=1; } memset(v,0,sizeof(v)); v[1]=1; for(int i=1;i<n;i++) { int u=0; int m=maxn; for(int j=2;j<=n;j++) { if(!v[j]&&m>d[j]) { u=j; m=d[j]; } } if(u) { v[u]=1; edges.push_back((edge){u,pre[u],d[u]}); g[u].push_back(edges.size()-1); edges.push_back((edge){pre[u],u,d[u]}); g[pre[u]].push_back(edges.size()-1); ans.push_back((edge){u,pre[u],d[u]}); for(int j=1;j<=n;j++) { if(!v[j]&&d[j]>p[u][j]) { pre[j]=u; d[j]=p[u][j]; } } } } for(int i=1;i<=n;i++) { memset(v,0,sizeof(v)); dfs(i,i,0); } int x=0,y=0,mm=maxn; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i][j]>p[i][j]&&p[i][j]<mm) { x=i; y=j; mm=p[i][j]; } } } if(x)ans.push_back((edge){x,y,p[x][y]}); else ans.push_back((edge){1,2,p[1][2]}); for(int i=0;i<n;i++) { printf("%d %d %d\n",ans[i].from,ans[i].to,ans[i].len); } } return 0; }