1. 小游戏（贪心）

本文介绍: 现在面临如下问题：他必须在一个中世纪的城堡里设防，城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。接下来的几行，每行按如下格式描述一个结点：结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 …… 结点标识符道路的数目。对于 n (0<n<=1500) 个结点，结点标识符是一个从 0 到 n – 1 的整数。这里和小学期的知识对应起来了。对于每组数据，各给出一个整数表示士兵的最少数目。你的任务是给出士兵的最少数目。第一行是结点的数目。

题干：

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

你的任务是给出士兵的最少数目。

输入：包含多组数据。每组数据表示一棵树，在每组数据中：

第一行是结点的数目。

接下来的几行，每行按如下格式描述一个结点：结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 …… 结点标识符道路的数目

或者

结点标识符 : (0)

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

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

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 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)↵	以文本方式显示 1↵ 2↵	1秒	64M	0

测试输入

期待的输出

测试用例 1

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)↵

以文本方式显示

1↵
2↵

1秒

64M

代码如下：

这里和小学期的知识对应起来了。（动态规划 dp[n][2]的设计）

#include &lt;iostream&gt;
#include &lt;cstring&gt;
using namespace std;

const int MAXN = 1505;
int dp[MAXN][2], visited[MAXN], link[MAXN][MAXN];
void DFS(int root)
{
    visited[root] = 1;
    for (int i = 0; link[root][i] != -1; ++i)
    {
        int m = link[root][i];
        if (!visited[m])
        {
            DFS(m);
            dp[root][1] += dp[m][0];
            dp[root][0] += min(dp[m][0], dp[m][1]);
        }
    }
    dp[root][0]++;
}
int main()
{
    int n;
    while (scanf("%d", &amp;n) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        memset(visited, 0, sizeof(visited));
        memset(link, 0, sizeof(link));
        int node, next, temp, root;
        for (int i = 0; i < n; i++)
        {
            scanf("%d:(%d)", &amp;node, &amp;next);
            root = (!i) ? node : root;
            int j = 0;
            for (; j < next; ++j)
            {
                cin &gt;&gt; temp;
                link[node][j] = temp;
            }
            link[node][j] = -1;
        }
        DFS(root);
        cout << min(dp[root][0], dp[root][1]) << endl;
    }
    return 0;
}