HDU2412+树形DP

第一道树形DP
详细见分析。。
View Code
  1 #include<stdio.h>
  2 #include<string>
  3 #include<stdlib.h>
  4 #include<map>
  5 #include<algorithm>
  6 #include<iostream>
  7 using namespace std;
  8 const int maxn = 205;
  9 const int maxm = 40005;
 10 struct node{
 11     int u,v,next;
 12 }edge[ maxm ];
 13 int cnt ,head[ maxn ];
 14 map<string,int>mp;
 15 
 16 void init(){
 17     cnt = 0;
 18     memset( head,-1,sizeof( head ) );
 19     mp.clear();
 20 }
 21 
 22 void addedge( int a,int b ){
 23     edge[ cnt ].u = a;
 24     edge[ cnt ].v = b;
 25     edge[ cnt ].next = head[ a ];
 26     head[ a ] = cnt++;
 27 }
 28 
 29 int dp[ maxn ][ 2 ];//dp[i][0]:第i个节点不去聚会的最多人数，dp[i][1]:第i个节点去聚会的最多人数
 30 //dp[i][0] = sigma of sons ( max(dp[j][0],dp[j][1]) );
 31 //dp[i][1] = sigma of sons ( dp[j][0] );
 32 int dup[ maxn ][ 2 ];
 33 //dup[i][j]=0:表示对于dp[i][j]这么多人参加聚会时，方案不是独一无二的。
 34 //dup[i][j]=1:表示对于dp[i][j]这么多人参加聚会时，方案是独一无二的。
 35 //如果儿子去和不去是一样的，那么父亲不去的话,肯定存在多种方案。如果父亲去的话，维持原状。
 36 //如果儿子不去的话存在多种方案，那么父亲去的话也会存在多种方案（因为父亲的值有儿子传过来，儿子不去有多种方案说明再加上一个父亲还是有多种方案）
 37 
 38 
 39 void dfs( int now ){
 40     dp[ now ][ 0 ] = 0;
 41     dp[ now ][ 1 ] = 1;
 42 
 43     dup[ now ][0]=1;  
 44     dup[ now ][1]=1;  
 45 
 46     for( int i=head[ now ];i!=-1;i=edge[ i ].next ){
 47         int v = edge[ i ].v;
 48         dfs( v );
 49         dp[ now ][ 0 ] += max( dp[ v ][ 0 ],dp[ v ][ 1 ] );
 50         dp[ now ][ 1 ] += dp[ v ][ 0 ];
 51         
 52         if( dp[ v ][0]==dp[ v ][1] ) dup[ now ][ 0 ] =0;
 53         if( dup[ v ][0]==0 ) dup[ now ][1]=0;
 54     }
 55 }
 56 
 57 int main(){
 58     int n;
 59     while( scanf("%d",&n)==1&&n ){
 60         string s1,s2;
 61         cin>>s1;
 62         init();
 63         int pcnt = 1;
 64         mp[ s1 ] = pcnt++;
 65         int num1,num2;
 66         for( int i=0;i<n-1;i++ ){
 67             cin>>s1>>s2;
 68 
 69             if( mp[s1]==0 ){
 70                 num1 = pcnt;
 71                 mp[s1]=pcnt++;
 72             }
 73             else num1 = mp[s1];
 74 
 75             if( mp[s2]==0 ){
 76                 num2 = pcnt;
 77                 mp[s2]=pcnt++;
 78             }
 79             else num2 = mp[s2];
 80 
 81             addedge( num2,num1 );
 82         }
 83         memset( dp,0,sizeof( dp ) );
 84         dfs( 1 );//树形DP
 85         if( n==1 ){
 86             printf("1 Yes\n");
 87             continue;
 88         }
 89         /*
 90         int ans = max( dp[1][0],dp[1][1] );
 91         int flag = 1;
 92         if( dp[1][0]==dp[1][0] ) flag = -1;
 93         for( int i=2;i<maxn&&flag==1;i++ ){
 94             if( dp[i][0]==ans || dp[i][1]==ans ){
 95                 flag = -1;
 96                 break;
 97             }
 98         }
 99         if( flag==-1 ) printf("%d No\n",ans);
100         else printf("%d Yes\n",ans);
101         //不懂为什么这种方法会错。。。
102         */
103         
104         if(dp[1][0]>dp[1][1] && dup[1][0])       printf("%d Yes\n",dp[1][0]);  //yes表示是独一无二的
105         else if(dp[1][1]>dp[1][0] && dup[1][1])  printf("%d Yes\n",dp[1][1]);  
106         else                                    printf("%d No\n",max(dp[1][0],dp[1][1]));  
107         
108     }
109     return 0;
110 }
keep moving...