Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
我们机房中了病毒，因此几乎什么都无法正常进入。为了解决这个病毒，我们花了好几天。终于在大家的共同努力下，病毒不再猖狂了。
我们的机房的所有计算机组成了一棵树，这是由于病毒，计算机无法两两完全连通的结果。所以，每台计算机能够直接连通的是
它的孩子计算机和父亲计算机。话说某天晚上，我们发现病毒绝迹了，但是我们无法确认是否真的消灭干净了。因此我们需要派
一些同学牺牲上课时间看守住所有的电脑两个小时，以确认没有任何病毒痕迹才能放心。我们当然想少耽误同学们的学习时间。
因此我们需要找出一种方案，使所需要的看守人员最少。直接连通的两台计算机只需要一个人即可看守住。
【输入格式】
输入文件中数据表示一棵树，描述如下：
第一行 N，表示树中结点的数目。
从第二行开始，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的
另一个结点标号r1，r2，…，rk。
对于一个n(1 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。
【输出格式】
输出数据只有一行，表示至少需要耽误多少学生的学习时间。
【数据规模】
对于 100% 的数据，保证n≤1500。
Sample Input1
4
0 1 1
1 2 2 3
2 0
3 0
Sample Output1
1
【样例说明】
将一名同学放在1号位置即可看守住所有的计算机。
【题解】
设f1[x]表示x这个节点要放人并且x与它的子树都已经被控制了;
设f2[x]表示x这个节点不放人并且x与它的子树都已经被控制了;
设f3[x]表示x这个节点没有被控制，但是x的子树都被控制了;
以上f都表示所需要的最小人数;
这题的根节点是确定的->1号节点;
【代码】
#include <cstdio>
#include <algorithm>
#include <vector>
const int MAXN = 1500 + 10;
using namespace std;
int n, f1[MAXN] = { 0 }, f2[MAXN] = { 0 }, f3[MAXN] = { 0 };
vector <int> a[MAXN];
void tree_dp(int x, int fa)
{
bool judge = false;
int len = a[x].size();
int aa = MAXN;
for (int i = 0; i <= len - 1; i++)
{
int y = a[x][i];
if (y == fa)
continue;
tree_dp(y, x);
f1[x] += min(f1[y], min(f2[y], f3[y]));//因为这个节点已经确定要放一个了，所以它的
//儿子是什么状态都无所谓；
f3[x] += f2[y];//f3是x没有被控制,f2[y]则表示y没有人监控。这正好对应了。直接转移;
if (f1[y] <= f2[y])//接下来要转移f2的状态
judge = true;//因为f2[x]是x这个点不放人监控但是被儿子监控了。
//所以如果一个节点x,它的所有儿子都没人在监控(即全都选择了f2状态).
//那么这节点x就不符合f2的状态了。
f2[x] += min(f1[y], f2[y]);
aa = min(aa, f1[y] - f2[y]);
//为了防止这种情况出现。我们要在它的儿子节点中找一个最优的点来监控这个x;
}
if (!judge) //如果儿子全都选择f2状态则要加一个最优的儿子节点监控它。
f2[x] += aa;
f1[x]++;//因为放了一个节点所以递增；
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int x, num, y;
scanf("%d%d", &x, &num);
x++;
for (int j = 1; j <= num; j++)
{
scanf("%d", &y);
y++;
a[x].push_back(y);
a[y].push_back(x);
}
}
tree_dp(1, 0);
printf("%d
", min(f1[1], f2[1]));//最后取根节点放或不放的最优值
return 0;
}