战略游戏
题目描述
Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的方法。现在他有个问题。
现在他有座古城堡，古城堡的路形成一棵树。他要在这棵树的节点上放置最少数目的士兵，使得这些士兵能够瞭望到所有的路。
注意：某个士兵在一个节点上时，与该节点相连的所有边都将能被瞭望到。
请你编一个程序，给定一棵树，帮 Bob 计算出他最少要放置的士兵数。
输入
输入数据表示一棵树，描述如下。
第一行一个数 N ，表示树中节点的数目。
第二到第 N+1 行，每行描述每个节点信息，依次为该节点编号 i，数值 k，k表示后面有 k条边与节点 i相连，接下来 k个数，分别是每条边的所连节点编号 r1,r2,?,rk。
对于一个有 N个节点的树，节点标号在 0到 N-1之间，且在输入文件中每条边仅出现一次。
输出
输出仅包含一个数，为所求的最少士兵数。
样例输入
4
0 1 1
1 2 2 3
2 0
3 0
样例输出
1
题解：
dp[u][0/1]表示u节点放不放士兵
如果子树的根节点不放士兵，那么根节点的子节点就必须全放士兵
dp[u][1]+=min(dp[t][0],dp[t][1]);
代码：
#include<bits/stdc++.h>
#define MAXN 1505
using namespace std;
int n;
int dp[MAXN][2],vis[MAXN];
vector<int> vc[MAXN];
int dfs(int u)
{dp[u][1]=1;for(int i=0;i<vc[u].size();++i){int t=vc[u][i];dfs(t);dp[u][0]+=dp[t][1];dp[u][1]+=min(dp[t][0],dp[t][1]);}
}
int main()
{scanf("%d",&n);int root;int a,b,c;for(int i=1;i<=n;++i){scanf("%d%d",&a,&b);for(int j=0;j<b;++j){scanf("%d",&c);vc[a].push_back(c);vis[i]=1;}}for(int i=0;i<n;++i)if(vis[i]==0){root=i;break;}dfs(root);printf("%d\n",min(dp[root][0],dp[root][1]));return 0;
}