Description:
Bob 喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的方法。现在他有个问题。
现在他有座古城堡,古城堡的路形成一棵树。他要在这棵树的节点上放置最少数目的士兵,使得这些士兵能够瞭望到所有的路。
注意:某个士兵在一个节点上时,与该节点相连的所有边都将能被瞭望到。
请你编一个程序,给定一棵树,帮 Bob 计算出他最少要放置的士兵数。
Analysis:
f[x][0/1] := x不放/放士兵时,以x为根的子树所需的最少士兵
0 : x不放,它的所有孩子都放,f[x][0] += f[y][1]
1: x放,它的儿子放或不放取最小,f[x][1] = min {f[y][0],f[y][1]}
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX_N = 1550;
struct tree{
int child[MAX_N];
}t[MAX_N];
int f[MAX_N][2],c[MAX_N],n,root;
void solve(int x)
{
f[x][0] = 0;
f[x][1] = 1;
if(t[x].child[0] == 0) return;
for(int j = 1;j <= t[x].child[0];++j)
{
solve(t[x].child[j]);
f[x][0] += f[t[x].child[j]][1];
f[x][1] += max(f[t[x].child[j]][0],f[t[x].child[j]][1]);
}
}
int main()
{
scanf("%d",&n);
for(int i = 0;i< n;++i)
{
int k,r;
scanf("%d%d",&k,&r);
t[i].child[0] = r;
for(int j = 1;j <= r;++j)
{
scanf("%d",&t[i].child[j]);
c[t[i].child[j]] = 1;
}
}
root = 0;
while (c[root])
{
root++;
}
solve(root);
printf("%d",max(f[root][0],f[root][1]));
return 0;
}