首页 > 代码库 > cf Inverse the Problem （最小生成树+DFS）
cf Inverse the Problem （最小生成树+DFS）
题意：
N个点。N行N列d[i][j]。
d[i][j]：结点i到结点j的距离。
问这N个点是否可能是一棵树。是输出YES，否则输出NO。
思路：
假设这个完全图是由一棵树得来的，则我们对这个完全图求最小生成树，得到原树。（画个图就明白）
故我们对完全图求最小生成树，然后用DFS从这棵树上的每个点出发，判断距离是否和矩阵d相同。
注意：
用vector存与每个点相连树枝的另一端，否则超时。用了vector也耗了1400多秒，限时2s。
代码：
#include <cstdio>#include <iostream>#include <string.h>#include <cstdlib>#include <algorithm>#include <queue>#include <vector>#include <cmath>#include <map>#include <stack>using namespace std;int const uu[4] = {1,-1,0,0};int const vv[4] = {0,0,1,-1};typedef long long ll;int const maxn = 50005;int const inf = 0x3f3f3f3f;ll const INF = 0x7fffffffffffffffll;double eps = 1e-10;double pi = acos(-1.0);#define rep(i,s,n) for(int i=(s);i<=(n);++i)#define rep2(i,s,n) for(int i=(s);i>=(n);--i)#define mem(v,n) memset(v,(n),sizeof(v))#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1struct node{ int x,y,len;};int n;int d[2005][2005], a[2005][2005];int fa[2005];node edge[4000005];vector<int> graph[2005];bool cmp(node a,node b){ return a.len<b.len;}int findFa(int x){ if(fa[x]!=x) fa[x]=findFa(fa[x]); return fa[x];}bool dfs(int start,int x,int fa,int weight){ if(d[start][x]!=weight){ return false; } int L=graph[x].size(); rep(i,0,L-1){ int v=graph[x][i]; if(v==fa) continue; bool t=dfs(start,v,x,weight+a[x][v]); if(!t) return false; } return true;}int main(){ scanf("%d",&n); rep(i,1,n) rep(j,1,n) scanf("%d",&d[i][j]); rep(i,1,n) if(d[i][i]!=0){ printf("NO\n"); return 0; } rep(i,1,n-1) rep(j,i+1,n){ if(d[i][j]==0 || (d[i][j]!=d[j][i])){ printf("NO\n"); return 0; } } int eNum=0; mem(a,0); rep(i,1,n-1) rep(j,i+1,n){ edge[++eNum].x=i, edge[eNum].y=j; edge[eNum].len=d[i][j]; } sort(edge+1,edge+1+eNum,cmp); rep(i,1,n) fa[i]=i; rep(i,1,n) graph[i].clear(); rep(i,1,eNum){ int xx=edge[i].x, yy=edge[i].y; int fx=findFa(xx), fy=findFa(yy); if(fx!=fy){ fa[fx]=fy; a[xx][yy]=a[yy][xx]=edge[i].len; graph[xx].push_back(yy); graph[yy].push_back(xx); } } int t=findFa(1); rep(i,2,n) if(findFa(i)!=t){ printf("NO\n"); return 0; } rep(i,1,n){ bool k=dfs(i,i,-1,0); //从顶点i出发 if(!k){ printf("NO\n"); return 0; } } printf("YES\n");}
cf Inverse the Problem （最小生成树+DFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。