1913: Strategic Game
题目描述
鲍勃喜欢玩电脑游戏，尤其是战略游戏，但有时他找不到足够快的解决方案，然后他很难过。现在他有以下问题:
他必须保卫一座中世纪的城市，这座城市的道路就像一棵树。他必须在节点上放置最小数量的士兵，以便他们能够观察所有边缘。你能帮他吗？
您的程序应该找到Bob必须为给定树放置的最小士兵数量。
输入文件包含多个文本格式的数据集。每个数据集代表一个树，具有以下描述：
节点的数量
每个节点的描述如下
节点标识符：（道路数）节点标识符1节点标识符2。。。节点标识符
或
节点标识符：（0）
对于n个节点（0<n<=1500），节点标识符是介于0和n-1之间的整数。每条边在输入数据中只出现一次。
例如，对于树：
解决方案是一个士兵（在节点1处）。
输出应打印在标准输出上。对于每个给定的输入数据集，在给出结果的单行中打印一个整数（最小士兵数量）。下表给出了一个示例：
Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?
Your program should find the minimum number of soldiers that Bob has to put for a given tree.
The input file contains several data sets in text format. Each data set represents a tree with the following desc
the number of nodes
the desc
node_identifier:(number_of_roads) node_identifier1 node_identifier2 ... node_identifier
or
node_identifier:(0)
The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.
For example for the tree:
the solution is one soldier ( at the node 1).
The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:
输入样例 复制
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