戰略游戲

題目描述

Bob喜歡玩電腦游戲，特別是戰略游戲。但是他經常無法找到快速玩過游戲的辦法。現在他有個問題。

他要建立一個古城堡，城堡中的路形成一棵樹。他要在這棵樹的結點上放置最少數目的士兵，使得這些士兵能了望到所有的路。

注意，某個士兵在一個結點上時，與該結點相連的所有邊將都可以被了望到。

請你編一程序，給定一樹，幫Bob計算出他需要放置最少的士兵.

輸入格式

第一行 N，表示樹中結點的數目。

第二行至第N+1行，每行描述每個結點信息，依次為：該結點標號i，k(后面有k條邊與結點I相連)。

接下來k個數，分別是每條邊的另一個結點標號r1，r2，...，rk。

對于一個n(0<n<=1500)個結點的樹，結點標號在0到n-1之間，在輸入數據中每條邊只出現一次。

輸出格式

輸出文件僅包含一個數，為所求的最少的士兵數目。

例如，對于如下圖所示的樹：

       0
1
2      3

答案為1（只要一個士兵在結點1上）。

輸入輸出樣例

輸入 #1

4
0 1 1
1 2 2 3
2 0
3 0

輸出 #1

1

分析：

樹的最大獨立集模板題。。。F[i][0]表示當前位置不放的最小值，F[i][1]表示當前位置放的最小值。

CODE：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1505;
struct node{
    int num;
    int child[M];
}k[M];
int f[M][2],a[M],n,root;
void dp(int x){
    f[x][1]=1;
    f[x][0]=0;
    if (k[x].num==0) return ;
    for (int i=1;i<=k[x].num;i++){
        dp(k[x].child[i]);
        f[x][0]+=f[k[x].child[i]][1];
        f[x][1]+=min(f[k[x].child[i]][0],f[k[x].child[i]][1]);
    }
}
int main() {
    cin>>n;
    for (int i=1;i<=n;i++){
        int x,y;
        cin>>x;
        cin>>k[x].num;
        for (int j=1;j<=k[x].num;j++){
            cin>>y;
            k[x].child[j]=y;
            a[y]=1;
        }
    }
    while (a[root]) root++;
    dp(root);
    cout<<min(f[root][0],f[root][1])<<endl;
    //system("pause");
    return 0;
}

?