Problem
小游戲
阿良很喜歡玩計算機(jī)游戲古毛，特別是戰(zhàn)略游戲弟劲，但是有時他不能盡快找到解所以常常感到很沮喪÷鲋矗現(xiàn)在面臨如下問題：他必須在一個中世紀(jì)的城堡里設(shè)防沥割，城堡里的道路形成一棵無向樹。要在結(jié)點上安排最少的士兵使得他們可以看到所有邊纫版。你能幫助他嗎床绪？
你的任務(wù)是給出士兵的最少數(shù)目。
輸入包含多組數(shù)據(jù)其弊。每組數(shù)據(jù)表示一棵樹癞己，在每組數(shù)據(jù)中：
第一行是結(jié)點的數(shù)目。
接下來的幾行梭伐，每行按如下格式描述一個結(jié)點：
結(jié)點標(biāo)識符 : ( 道路的數(shù)目 ) 結(jié)點標(biāo)識符1 結(jié)點標(biāo)識符2 ...... 結(jié)點標(biāo)識符道路的數(shù)目
或者
結(jié)點標(biāo)識符 : (0)
對于 n (0<n<=1500) 個結(jié)點痹雅，結(jié)點標(biāo)識符是一個從 0 到 n - 1 的整數(shù)。每條邊在測試用例中只出現(xiàn)一次糊识。
對于每組數(shù)據(jù)绩社，各給出一個整數(shù)表示士兵的最少數(shù)目.
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;
}
