UVA1292-----Strategic game-----樹形DP解決樹上的最小點覆蓋問題

題目意思： 給你一棵樹 要你在樹上的一些點上放置士兵，放的節點上面是一個 問你怎樣放最少的能使所有的邊被照顧到，一個士兵可以同時照顧和他所處節點相連的邊 解題思路： 最少點覆蓋問題 可以用樹形DP解決 我們把無根樹抽象成一棵有根樹，0為樹根 對於任意一個節點i來說，設dp[i][0]表示在該節點不放士兵 dp[i][1]表示在該節點放置士兵 那麼結合他的子節點就可以得到狀態轉移方程 dp[i][1] = sum(dp[k][0])+1  k為i的子節點，下同，因為本節點沒放，則子節點一定要放 dp[i][0] = sum( min(dp[k][0],dp[k][1]) )  因為本節點放了，所以取子節點放和不放的最小值 最後答案就是min( dp[0][0] ,dp[0][1] ) 雖然是一道很簡單的樹形DP，但是對與學習樹形DP很有啟發意義 下面上代碼：

#include<iostream>  
#include<vector>  
#include<cstring>  
#include<cstdio>  
#include<algorithm>  
#include<cmath>  
using namespace std;  
  
const int maxn = 1600;  
int dp[maxn][2];  
int n;  
vector<int> tree[maxn];  
  
int min(int a,int b)  
{  
    return a<b?a:b;  
}  
  
void dfs(int fa,int now)  
{  
    dp[now][0] = 0;  
    dp[now][1] = 1;  
  
    int len = tree[now].size();  
    int i;  
  
    for(i=0;i<len;i++)  
    {  
        int t=tree[now][i];  
        if(t!=fa)  
        {  
            dfs(now,t);  
            dp[now][0] += dp[t][1];  
            dp[now][1] += min(dp[t][0],dp[t][1]);  
        }  
    }  
      
}  
  
  
int main()  
{  
    while(~scanf("%d",&n))  
    {  
        int i;  
        for(i=0;i<n;i++)  
        {  
            tree[i].clear();  
        }  
        for(i=0;i<n;i++)  
        {  
            int b;  
            int a;  
            int j;  
            scanf("%d:(%d)",&a,&b);  
            for(j=0;j<b;j++)  
            {  
                int x;  
                scanf("%d",&x);  
                tree[a].push_back(x);  
                tree[x].push_back(a);  
            }  
        }  
        dfs(-1,0);  
        cout<<min(dp[0][0],dp[0][1])<<endl;  
    }  
    return 0;  
}