注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2378Tree Cutting题解  

2014-03-26 20:16:20|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                割树
                                       BY   LGS
题目大意:给你一棵树,求其重心。重心定义见度娘。

题解:直接模拟即可,当然最好用BFS防止爆栈。对于每一颗树,我们可以用调整法证明每棵树,一定有重心,所以跟本不需要输出NONE,直接做。对于每个结点i,只要判断它所有儿子中最大结点的值《=N/2并且N-D[I]《=N/2把就计入答案。D[I]=所有儿子结点个数+1

总解:模拟;
代码:
  • Source Code
  • #include<cstdio>
    #define maxn 40000
    using namespace std;
    struct node{int b,next;}g[maxn];
    int i,j,n,k,m,tot,x,y,t,w,u;
    int fa[maxn],que[maxn],ans[maxn],dp[maxn];
    bool q[maxn];
    int max(int a,int b){return (a>b)?a:b;}
    void add(int a,int b)
     {
     tot++;g[tot].b=b;
     g[tot].next=fa[a];
     fa[a]=tot;
     }
    int main()
    {
     scanf("%d",&n);tot=0;
     for (i=1;i<=n-1;i++)
         {
         scanf("%d%d",&x,&y);
         add(x,y);add(y,x);
         }
    t=0;w=1;que[1]=1;q[1]=true;
    while (t<w){
               t++;
               for (i=fa[que[t]];i;i=g[i].next)
                        if (!q[g[i].b])
                              {
                              w++;que[w]=g[i].b;q[g[i].b]=true;
                              }
                }
    for (i=w;i>=1;i--){
             int k=que[i];u=0;
             for (j=fa[k];j;j=g[j].next)
                                        {
                                u=max(u,dp[g[j].b]);
                                dp[k]+=dp[g[j].b];
                                        }
             dp[k]++;if ((u<=n/2)&&(n-dp[k]<=n/2)) ans[k]=1;
                      } 
    for (i=1;i<=n;i++)if (ans[i]) printf("%d\n",i);
    return 0;
    } 

  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018