Codeforces 765E - Tree Folding 【树，dfs/bfs】

2019-11-08 01:55:08

字体：大中小

来源：转载

供稿：网友

题目：http://codeforces.com/contest/765/PRoblem/E

题意：

给你一棵树，可以在这棵树上进行若干次操作，每次操作可以把两条长度相同的链，根据一个中点合并在一起。然后问你经过若干次合并之后，最后的最短链长度是多少。如果不能合并成一条链，输出-1.

分析：

拓扑排序，每次我们从度数为1的点出发bfs。然后往上合并，如果遇到交叉点，我们就合并链。我们用一个set来合并就好了，如果两条链长度一样，在set里面自动就合并了。显然能够bfs的点的set里面只有一个数。而且只能有一个点的set里面有两个数。最后扫一遍check一下就好了。 bfs：http://www.cnblogs.com/qscqesze/p/6401615.html dfs：http://www.cnblogs.com/RUSH-D-CAT/p/6404742.html

代码：

#include<bits/stdc++.h>using namespace std;const int maxn = 2e5+7;vector<int> g[maxn];int n,vis[maxn],d[maxn];set<int> S[maxn];int main(){ scanf("%d",&n); for(int i=1; i<n; i++) { int a,b; scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); d[a]++; d[b]++; } queue<int> Q; for(int i=1; i<=n; i++) { if(g[i].size()==1) { Q.push(i); S[i].insert(0); } } while(!Q.empty()) { int now = Q.front(); vis[now]=1; Q.pop(); for(int i=0; i<g[now].size(); i++) { int v = g[now][i]; if(vis[v])continue; S[v].insert((*S[now].begin())+1); d[v]--; if(d[v]==1&&S[v].size()==1) { Q.push(v); } } } int ans = 0,num2 = 0; for(int i=1; i<=n; i++) { if(S[i].size()==0) { cout<<"-1"<<endl; return 0; } if(S[i].size()>2) { cout<<"-1"<<endl; return 0; } if(S[i].size()==1) { ans=max(ans,*S[i].begin()); } if(S[i].size()==2) { ans=max(ans,*S[i].begin()+*S[i].rbegin()); num2++; } } if(num2>1) { cout<<"-1"<<endl; return 0; } while(ans%2==0) { ans/=2; } cout<<ans<<endl;}

上一篇：JVM以及垃圾回收器的工作原理

下一篇：Groovy中Mixin注入

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注