POJ.1655 Balancing Act POJ.3107 Godfather（树的重心）

关于树的重心：百度百科

有关博客：http://blog.****.net/acdreamers/article/details/16905653

1.Balancing Act

To POJ.1655 Balancing Act

题目大意：

　　有t组数据。每组数据给出n个点和n-1条边，构成一棵树，求该树的重心及删掉该点后形成的每棵子树的节点数。

代码：

 #include<cctype>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 const int N=;

 int n,cnt,H[N<<],Ans,size,son[N];
 bool vis[N];
 struct Edge
 {
     int to,nxt;
 }e[N<<];

 void read(int &now)
 {
     now=;char c=getchar();
     while(!isdigit(c))c=getchar();
     while(isdigit(c))now=(now<<)+(now<<)+c-'',c=getchar();
 }

 void AddEdge(int u,int v)
 {
     e[++cnt].to = v;
     e[cnt].nxt = H[u];
     H[u] = cnt;
 }

 void Init()
 {
     Ans=size=0x7fffffff;
     for(int i=;i<=n;++i)
       vis[i]=son[i]=H[i]=;
     cnt=;
     read(n);
     int a,b;
     for(int i=;i<n;++i)
       read(a),read(b),AddEdge(a,b),AddEdge(b,a);
 }

 void DFS(int cur)
 {
     vis[cur]=;
     son[cur]=;
     int tmp=;
     for(int i=H[cur];i;i=e[i].nxt)
     {
         int to=e[i].to;
         if(!vis[to])
         {
             DFS(to);
             son[cur]+=son[to]+;
             tmp=max(tmp,son[to]+);
         }
     }
     tmp=max(tmp,n-son[cur]-);
     if(size>tmp ||size==tmp&&Ans>cur)
     {
         Ans=cur;
         size=tmp;
     }
 }

 int main()
 {
     int t;
     read(t);
     while(t--)
     {
         Init();
         DFS();
         printf("%d %d\n",Ans,size);
     }
     return ;
 }

Balancing Act

2.Godfather

To POJ.3107 Godfather

题目大意：

　　按升序输出该树的重心。

代码：

 #include<cstdio>
 #include<cctype>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 const int N=;

 int n,cnt,tot,size,H[N<<],Ans[N],son[N];
 bool vis[N];
 struct Edge
 {
     int to,nxt;
 }e[N<<];

 void read(int &now)
 {
     now=;char c=getchar();
     while(!isdigit(c))c=getchar();
     while(isdigit(c))now=(now<<)+(now<<)+c-'',c=getchar();
 }

 void AddEdge(int u,int v)
 {
     e[++cnt].to = v;
     e[cnt].nxt = H[u];
     H[u] = cnt;
 }

 void Init()
 {
     memset(H,,sizeof H);
     memset(vis,,sizeof vis);
     memset(Ans,0x3f,sizeof Ans);
     size=0x7fffffff;
     cnt=tot=;
     read(n);
     int x,y;
     for(int i=;i<n;++i)
       read(x),read(y),AddEdge(x,y),AddEdge(y,x);
 }

 void DFS(int cur)
 {
     vis[cur]=;
     son[cur]=;
     int tmp=;
     for(int i=H[cur];i;i=e[i].nxt)
     {
         int to=e[i].to;
         if(!vis[to])
         {
             DFS(to);
             son[cur]+=son[to]+;
             tmp=max(tmp,son[to]+);
         }
     }
     tmp=max(tmp,n-son[cur]-);
     if(size>tmp)
     {
         size=tmp;
         tot=;
         Ans[tot]=cur;
     }
     else if(size==tmp)
     {
         Ans[++tot]=cur;
     }
 }

 int main()
 {
     Init();
     DFS();
     sort(Ans+,Ans++tot);
     for(int i=;i<=tot;++i)
       printf("%d ",Ans[i]);
     return ;
 }

Godfather