Problem

小游戏

阿良很喜欢玩计算机游戏，特别是战略游戏，但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题：他必须在一个中世纪的城堡里设防，城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗？
你的任务是给出士兵的最少数目。

输入包含多组数据。每组数据表示一棵树，在每组数据中：
第一行是结点的数目。

接下来的几行，每行按如下格式描述一个结点：

结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 ...... 结点标识符道路的数目

或者

结点标识符 : (0)

对于 n (0<n<=1500) 个结点，结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。

对于每组数据，各给出一个整数表示士兵的最少数目.

test input

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

test output

1
2

ac code

//
//  main.cpp
//  DP或贪心
//
//  Created by jetviper on 2017/3/18.
//  Copyright © 2017年 awlsx. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string.h>
struct {
    int childCount=0;
    int childArr[1500];
}node[1500];
int n,root;
int father[1500],dp[1500][2];

void input(){
    int no,chnum,x;
        for (int i = 0; i < n; i++) {
            
            scanf("%d:(%d)", &no, &chnum);
        
            for (int j = 0; j < chnum; j++) {
                scanf("%d", &x);
                father[x] = no;
                node[no].childArr[node[no].childCount++] = x;

            }
           
        }
}
int min(int a,int b){
    return a>b?b:a;
}
void dpSearch(int root){
    
    if (node[root].childCount == 0) {
        dp[root][0] = 0;
        dp[root][1] = 1;
        return;
    }

        for (int i=0; i<node[root].childCount; i++) {
            dpSearch(node[root].childArr[i]);
        }
        for (int i=0; i<node[root].childCount; i++) {
            dp[root][0] += dp[node[root].childArr[i]][1];
            dp[root][1] += min(dp[node[root].childArr[i]][1], dp[node[root].childArr[i]][0]);
        }
        dp[root][1]++;
        return;

    
}
void setMen(){
    for (int i=0; i<=n; i++) {
        father[i]=-1;
        node[i].childCount = 0;
    }

    memset(dp, 0, sizeof(dp));
}
int main(int argc, const char * argv[]) {
   

    while (scanf("%d",&n)!=EOF) {
        setMen();
        int no,chnum,x;
        for (int i = 0; i < n; i++) {
            
            scanf("%d:(%d)", &no, &chnum);
            
            for (int j = 0; j < chnum; j++) {
                scanf("%d", &x);
                father[x] = no;
                node[no].childArr[node[no].childCount++] = x;
                
            }
            
        }
        for (int i = 0; i < n; i++) {
            if (father[i] == -1) {
                root = i;
                break;
                }
            }
        dpSearch(root);
        
        printf("%d\n",min(dp[root][0],dp[root][1]));
        
        
    }
    
    
    
    
    
    return 0;
}