独立博客: 哲学与程序

哲学与程序

patriking Algorithm@POJ3107(树形动态规划)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3107
题意:给定一棵无根树,删除树中一个节点,剩下各子树的包含的节点数最大值最小,问树中有多少个这样的节点?
解法:任意选择一个节点,作为根,进行遍历。对一个节点V,设其子节点为cv[1..k],f[v]为以节点v为根的子树包含的节点数。
对 于每一个节点V,删除V之后剩下子树含有的节点数中最大分别为 max{ f[cv[1]],f[cv[2]],....f[cv[k]],SumNode-(f[cv[1]]+f[cv[2]]+....+f[cv[k]]) },一次遍历即可求出所有删除一个节点后的最大子树包含的节点数。
//7044398    Oestrus    3107    Accepted    4164K    688MS    G++    1595B    2010-06-11 22:11:19
#include<iostream>
#include
<vector>
#include
<algorithm>
#include
<stdio.h>
#define MAXN 50005 
using namespace std;
vector
<int>ansNode;
int maxNumNode;
int n, f[MAXN];
int pointTree[MAXN];
struct Tree{
    
int x,y;
}tree[MAXN
*2];
int len;
bool cmp(struct Tree a, struct Tree b)
{
    
return a.x<b.x;
}
int treedp(int parentNode,int thisNode){
    
int maxNode=0;
    
int sumChildNode=0;
    
int index=pointTree[thisNode];
    
do{
        
int childNode=tree[index].y;
        
if(childNode != parentNode)
        {
            f[childNode]
=treedp(thisNode,childNode);
            sumChildNode
+=f[childNode];
            
if(f[childNode]>maxNode)maxNode=f[childNode];
        }
        index
++;
    }
while(index<len && tree[index].x==tree[index-1].x);
    
if(maxNode<n-sumChildNode-1)maxNode=n-sumChildNode-1;
    
if(maxNode<maxNumNode){
        maxNumNode
=maxNode;
        ansNode.clear();
        ansNode.push_back(thisNode);
    }
else if(maxNode==maxNumNode){
        ansNode.push_back(thisNode);
    }
    
return sumChildNode+1;
}

int main(int argc,int *argv[])
{
    
while(scanf("%d",&n)!=EOF){
        len
=0;
        
for(int i=1;i<n;i++){
            
int x,y;
            scanf(
"%d%d",&x,&y);
            tree[len].x
=x;
            tree[len
++].y=y;
            tree[len].x
=y;
            tree[len
++].y=x;
        }
        sort(tree,tree
+len,cmp);
        pointTree[tree[
0].x]=0;
        
for(int i=1;i<len;i++){
            
if(tree[i].x != tree[i-1].x)
                pointTree[tree[i].x] 
= i;
        }
        ansNode.clear();
        maxNumNode
=n;
        treedp(
-1,1);
        sort(ansNode.begin(),ansNode.end());
        
for(int i=0;i<ansNode.size();i++)
            printf(
"%d ",ansNode[i]);
    }
    
return 0;
}

posted on 2011-01-07 17:28 哲学与程序 阅读(206) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序