本文主要是介绍hnu 12947 Absurdistan Roads，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hnu 12947 网址 http://acm.hnu.cn/online/?action=problem&type=show&id=12947
给出n 和 n*n的矩阵 a(i,j)表示i 到j 的距离 然后求n条边 是的这个最短路成立
用求最小生成树的方法求出n-1条边 这n-1条边肯定是有用的 主要是如何求出第n条边
用floyd求出任意两点之间的最短距离
然后找出不满足最短距离的边 把它输出 如果都满足那就随便输出啦
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 100100
#define INF 0x3f3f3f3f
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOV(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64using namespace std;
int n,cnt;struct edge
{int u,v;int len;bool operator <(const edge p)const{return len<p.len;}
};
edge e[4000005];
int mp[2005][2005];int parent[2010];void init()
{MEM(mp,INF);for(int i=0;i<n;i++)parent[i]=-1;
}int Find(int x)
{int s;for(s=x;parent[s]>=0;s=parent[s]);while(s!=x){int tmp=parent[x];parent[x]=s;x=tmp;}return s;
}void Union(int R1,int R2)
{int r1=Find(R1),r2=Find(R2);int tmp=parent[r1]+parent[r2];if(parent[r1]>parent[r2]){parent[r1]=r2;parent[r2]=tmp;}else{parent[r2]=r1;parent[r1]=tmp;}
}void Kruskal()
{int x,y;init();/* if(n==2){printf("%d %d %d\n",e[0].u+1,e[0].v+1,e[0].len);printf("%d %d %d\n",e[0].u+1,e[0].v+1,e[0].len);return;}*/int num=0;for(int i=0;i<cnt;i++){x=e[i].u; y=e[i].v;if(Find(x)!=Find(y)){num++;printf("%d %d %d\n",e[i].u+1,e[i].v+1,e[i].len);mp[e[i].u][e[i].v]=mp[e[i].v][e[i].u]=e[i].len;Union(x,y);}if(num>=(n-1)) break;}
// printf("%d %d %d\n",e[0].u+1,e[0].v+1,e[0].len);
}void floyd()
{for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(mp[i][k]==INF) break;mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);}
}int main()
{
//freopen("ceshi.txt","r",stdin);int cs=0;while(scanf("%d",&n)!=EOF){cnt=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){int x;scanf("%d",&x);if(i>j){e[cnt].u=i; e[cnt].v=j;e[cnt].len=x;cnt++;}}}sort(e,e+cnt);if(cs>0)puts("");cs++;Kruskal();floyd();int k;for(k=0;k<cnt;k++){if(mp[e[k].u][e[k].v]!=e[k].len){printf("%d %d %d\n",e[k].u+1,e[k].v+1,e[k].len);break;}}if(k==cnt){printf("%d %d %d\n",e[0].u+1,e[0].v+1,e[0].len);}}return 0;
}这篇关于hnu 12947 Absurdistan Roads的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
