首页 > 代码库 > Codeforces Round #270 D Design Tutorial: Inverse the Problem --MST + DFS
Codeforces Round #270 D Design Tutorial: Inverse the Problem --MST + DFS
题意：给出一个距离矩阵，问是不是一颗正确的带权树。
解法：先按找距离矩阵建一颗最小生成树，因为给出的距离都是最短的点间距离，然后再对每个点跑dfs得出应该的dis[][]，再对比dis和原来的mp是否一致即可。
首先还要判断一些东西。具体看代码吧。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <vector>using namespace std;#define N 2007struct Edge{ int u,v,w;}edge[N*N];int a[N][N],fa[N],dis[N][N];vector<pair<int,int> > G[N];int cmp(Edge ka,Edge kb) { return ka.w < kb.w; }int findset(int x){ if(x != fa[x]) fa[x] = findset(fa[x]); return fa[x];}void dfs(int u,int fa,int ori){ for(int i=0;i<G[u].size();i++) { int v = G[u][i].first; if(v == fa) continue; dis[ori][v] = dis[ori][u] + G[u][i].second; dfs(v,u,ori); }}int main(){ int n,i,j; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%I64d",&a[i][j]); int tag = 1; for(i=1;i<=n;i++) { fa[i] = i; for(j=1;j<=n;j++) { if((i == j && a[i][j] != 0)||(i != j && a[i][j] == 0)||(a[i][j] != a[j][i])) { tag = 0; break; } } if(!tag) break; } if(!tag) { puts("NO"); continue; } int tot = 0; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) edge[tot].u = i, edge[tot].v = j,edge[tot++].w = a[i][j]; sort(edge,edge+tot,cmp); for(i=0;i<tot;i++) { int u = edge[i].u, v = edge[i].v, w = edge[i].w; int fx = findset(u), fy = findset(v); if(fx != fy) { G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); fa[fx] = fy; } } for(i=1;i<=n;i++) { dis[i][i] = 0; dfs(i,0,i); for(j=1;j<=n;j++) { if(a[i][j] != dis[i][j]) { tag = 0; break; } } if(!tag) break; } if(!tag) puts("NO"); else puts("YES"); } return 0;}
Codeforces Round #270 D Design Tutorial: Inverse the Problem --MST + DFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。