首页 > 代码库 > POJ 1655 Balancing Act(求树的重心)
POJ 1655 Balancing Act(求树的重心)
题目大意:
就是要求树的重心,重心的定义就是删除这个点使得森林尽量平衡。
也可以让分治子树的时候使得每颗子树的数量在nlogn以内。
思路分析:
son [x] 表示x的子树的数量 不包括自己。
balance 表示最大的森林的节点数。
最后我们要让最大的balance 最小。
balance = max (balance ,n - 1 - son[x] , son[j] +1)..
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define maxn 20005 #define inf 0x3f3f3f3f using namespace std; int tot; int to[maxn<<1]; int next[maxn<<1]; int head[maxn]; int son[maxn]; int n; void init() { tot=0; memset(head,0,sizeof head); } void addedge(int u,int v) { tot++; next[tot]=head[u]; to[tot]=v; head[u]=tot; } bool vis[maxn]; int ans,ansize; void dfs(int now)//求树的重心 { son[now]=0; int balance=0; for(int p = head[now] ; p ;p = next[p]) { int v = to[p]; if(vis[v])continue; vis[v]=true; dfs(v); son[now]+=son[v]+1; balance=max(balance,son[v]+1); } balance=max(balance,n-1-son[now]); if(balance<ansize || balance==ansize && now<ans) { ans=now,ansize=balance; } } int main() { int T; scanf("%d",&T); while(T--) { init(); scanf("%d",&n); for(int i=2;i<=n;i++) { int s,e; scanf("%d%d",&s,&e); addedge(s,e); addedge(e,s); } memset(vis,false,sizeof vis); ansize=inf; vis[1]=true; dfs(1); printf("%d %d\n",ans,ansize); } return 0; }
POJ 1655 Balancing Act(求树的重心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。