題面:http://poj.org/problem?id=1655

本題是求樹的重心裸題。Code: #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int N=20005; int n,f[N],size[N]; struct Node{int v,Next; }Edge[N*2]; int head[N],Cnt; void Push(int u,int v){++Cnt;Edge[Cnt].v=v;Edge[Cnt].Next=head[u];head[u]=Cnt; } void dfs(int u,int fa){size[u]=1;for(int i=head[u];i;i=Edge[i].Next){int v=Edge[i].v;if(v==fa){continue;}dfs(v,u);f[u]=max(f[u],size[v]);size[u]+=size[v];}f[u]=max(f[u],n-size[u]); } int main(){int t,u,v;scanf("%d",&t);while(t--){memset(head,0,sizeof(head));memset(f,0,sizeof(f));Cnt=0;scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);Push(u,v);Push(v,u);}dfs(1,0);int ans1=1,ans2=f[1];for(int i=2;i<=n;i++){if(ans2>f[i]){ans1=i;ans2=f[i];}}printf("%d %d\n",ans1,ans2);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ukcxrtjr/p/11243518.html

總結(jié)

以上是生活随笔為你收集整理的POJ1655 Balancing Act的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。