Hoj 2500 Party at Hali-Bula

樹形DP典型題。求最大獨立集。

本題難在唯一性的判斷上。

沒接觸樹形DP以前，我以為本題的最大獨立集的值應該是(1 + 3 + 5 + 7 + ...)層的和 與 (2 + 4 + 6 + 8 + 10 + ...)層的和的最大值。其實不對。

因為如果父節點是不選擇的，而子節點既可以不選擇也可以選擇；但是如果父節點是選擇的，那麼子節點只能是不選擇的。所以情況是多樣化的，只能用樹形DP來做。

代碼如下：

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <vector>  
#include <map>  
#include <algorithm>  
 
using namespace std; 
 
#define Maxn 205  
 
int n; 
vector<int> p[Maxn]; 
map<string,int> m; 
string s,s1,s2; 
//dp[i][1]代表選擇i點,dp[i][0]代表不選擇  
int dp[Maxn][2]; 
//flag[i][1]代表選擇i點後,i為根的樹的最大獨立集不唯一  
bool flag[Maxn][2]; 
 
void dfs(int u) 
{ 
    for(int i=0;i<p[u].size();i++) 
    { 
        int v = p[u][i]; 
        dfs(v); 
        dp[u][1] += dp[v][0]; 
        dp[u][0] += max(dp[v][0],dp[v][1]); 
        if(dp[v][0] == dp[v][1] || (dp[v][0]>dp[v][1] && flag[v][0] == false) || (dp[v][0]<dp[v][1] && flag[v][1] == false)) 
        { 
            flag[u][0] = false; 
        } 
        if(flag[v][0] == false) 
        { 
            flag[u][1] = false; 
        } 
    } 
    dp[u][1]++; 
} 
int main() 
{ 
    #ifndef ONLINE_JUDGE  
        freopen("in.txt","r",stdin); 
    #endif  
    while(scanf(" %d",&n)!=EOF && n!=0) 
    { 
        for(int i=0;i<Maxn;i++) p[i].clear(); 
        m.clear(); 
        memset(dp,0,sizeof(dp)); 
        memset(flag,true,sizeof(flag)); 
        int cnt = 1; 
        cin>>s; 
        m[s] = 1; 
        for(int i=1;i<n;i++) 
        { 
            cin>>s1>>s2; 
            if(m[s1] == 0) m[s1] = ++cnt; 
            if(m[s2] == 0) m[s2] = ++cnt; 
            p[m[s2]].push_back(m[s1]); 
        } 
        dfs(1); 
        printf("%d ",max(dp[1][0],dp[1][1])); 
        if((dp[1][0]>dp[1][1] && flag[1][0] == true) || (dp[1][0]<dp[1][1] && flag[1][1] == true)) 
            printf("Yes\n"); 
        else 
            printf("No\n"); 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define Maxn 205

int n;
vector<int> p[Maxn];
map<string,int> m;
string s,s1,s2;
//dp[i][1]代表選擇i點,dp[i][0]代表不選擇
int dp[Maxn][2];
//flag[i][1]代表選擇i點後,i為根的樹的最大獨立集不唯一
bool flag[Maxn][2];

void dfs(int u)
{
    for(int i=0;i<p[u].size();i++)
    {
        int v = p[u][i];
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0],dp[v][1]);
        if(dp[v][0] == dp[v][1] || (dp[v][0]>dp[v][1] && flag[v][0] == false) || (dp[v][0]<dp[v][1] && flag[v][1] == false))
        {
            flag[u][0] = false;
        }
        if(flag[v][0] == false)
        {
            flag[u][1] = false;
        }
    }
    dp[u][1]++;
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    while(scanf(" %d",&n)!=EOF && n!=0)
    {
        for(int i=0;i<Maxn;i++) p[i].clear();
        m.clear();
        memset(dp,0,sizeof(dp));
        memset(flag,true,sizeof(flag));
        int cnt = 1;
        cin>>s;
        m[s] = 1;
        for(int i=1;i<n;i++)
        {
            cin>>s1>>s2;
            if(m[s1] == 0) m[s1] = ++cnt;
            if(m[s2] == 0) m[s2] = ++cnt;
            p[m[s2]].push_back(m[s1]);
        }
        dfs(1);
        printf("%d ",max(dp[1][0],dp[1][1]));
        if((dp[1][0]>dp[1][1] && flag[1][0] == true) || (dp[1][0]<dp[1][1] && flag[1][1] == true))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}