HDU 1520 Anniversary party-白红宇

HDU 1520 Anniversary party

阅读量：4703 次

发布时间：2019-06-10

本文共 1044 字，大约阅读时间需要 3 分钟。

题目意思：有n个人，他们的关系是一棵树，每个人有一个欢乐度，举行一个聚会，邀请个人里的一些人，但是如果两个人的关系是上下级，他们最多一个被邀请

int dp[][2] dp[][0]表示不邀请这个人得到的最大欢乐度，dp[][1]表示邀请这个人得到的最大欢乐度

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 using namespace std;12 int dp[6200][2];13 vector
               
                ko[6200];14 int n,pe[6200],fa[6200],ben,vit[6200][2];15 int dfs(int pos,int way)16 {17 if(ko[pos].size()==0)18 {19 if(way)20 dp[pos][way]=pe[pos];21 else22 dp[pos][way]=0;23 return dp[pos][way];24 }25 if(vit[pos][way])26 return dp[pos][way];27 if(way)28 dp[pos][way]+=pe[pos];29 for(int i=0;i
                
                 >n)59 {60 for(int i=1;i<=n;i++)61 scanf("%d",&pe[i]);62 for(int i=1;i<=n;i++)63 ko[i].clear();64 int a,b;65 memset(fa,-1,sizeof(fa));66 while(scanf("%d%d",&a,&b)&&(a+b)!=0){67 ko[b].push_back(a);68 fa[a]=b;69 }70 for(int i=1;i<=n;i++)71 if(fa[i]==-1)72 ben=i;73 solve();74 }75 }