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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj1655Balancing Act题解  

2014-03-31 22:14:28|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                    重心
                                         BY   LGS
题目大意:找一颗树的重心,重心定义:删除此点留下的所有子树最大节点数最小。

题解:DFS或者BFS+DP(防止爆栈),我选择第二种的。NUM[I]记录i结点以下包含自己的节点数。DP[I]表示i结点儿子中最大的节点数。DP[I]=MAX(DP[I],num[U]);最后DP[I]=MAX(DP[I],N-NUM[I]);

总结:重心基础题
代码:
  • Source Code
  • #include<cstdio>
    #include<cstring>
    #define maxn 40001
    using namespace std;
    int l,tot,i,j,k,n,t,w,x,ans,flag,y,fa[maxn],queue[maxn],dp[maxn],num[maxn];
    bool b[maxn];
    struct node{int end,next;}g[maxn*2];
    void add(int a,int b)
     {
     g[++tot].end=b;
     g[tot].next=fa[a];fa[a]=tot;
     }
    int max(int a,int b){return (a>b)?a:b;}
    int main()
    {
     scanf("%d",&l);
     while (l){
              l--;
        scanf("%d",&n);
        tot=0;memset(b,false,sizeof(b));
        memset(fa,0,sizeof(fa));memset(dp,0,sizeof(dp));memset(num,0,sizeof(num));
        memset(g,0,sizeof(g));memset(queue,0,sizeof(queue));
        for (i=1;i<=n-1;i++) {
                             scanf("%d%d",&x,&y);
                              add(x,y);add(y,x);
                              }
    t=0;k=1;queue[1]=1;b[1]=true;
    while (t<k){
               t++;w=queue[t];
         for (i=fa[w];i;i=g[i].next)if (!b[g[i].end]){
                      b[g[i].end]=true;queue[++k]=g[i].end;
                                                     }
               }
    memset(b,false,sizeof(b));
    for (i=n;i>=1;i--){
                   w=queue[i];b[w]=true;
            for (j=fa[w];j;j=g[j].next)if (b[g[j].end])
                      {dp[w]=max(dp[w],num[g[j].end]);num[w]+=num[g[j].end];}
                      num[w]++;
                      }
            ans=99999999;flag==0;
    for (i=1;i<=n;i++)if (max(n-num[i],dp[i])<ans){ans=max(n-num[i],dp[i]);flag=i;}
    printf("%d %d\n",flag,ans);
             }
    return 0;
    }
    

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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