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 description:
the number of nodes
the description of each node in the following format
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:
Input
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)
Output
1
2
题意：在一棵树里面查找最小的点覆盖。
_______________________________________________________________________________________________________
求最小点覆盖，匈牙利算法。
匈牙利算法，求二分图最大匹配。
一些定义，自己的话：
二分图：可以把图中的点看出人，男女分成2组，男男，女女同性之间没有直接连边。
匹配：二分图中，2中中各取一个人，有边相连，就是一个匹配。就是两夫妻一个在这边一个在那边，这就是匹配，当然一夫一妻制。
最大匹配：最多可组成的夫妻对数就是了。
下面有一些定理（引自网络）：
(1)二分图的最小顶点覆盖
最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。
Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。
(2)DAG图的最小路径覆盖
用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。
结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）
(3)二分图的最大独立集
最大独立集问题： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值
结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）
匈牙利算法可以参考程序中的代码，如果看不懂（本人水平实在有限）可以参考http://blog.csdn.net/dark_scope/article/details/8880547 真正的通俗易懂！
双向边要除以2，切记！
_______________________________________________________________________________________________________
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm> using namespace std;
const int maxn=;
int n;
int head[maxn],js;
struct edge
{
int u,v,next;
}e[maxn*];
int link[maxn];
bool vis[maxn];
void init()
{
memset(e,,sizeof(e));
memset(head,,sizeof(head));
js=;
memset(link,-,sizeof(link));
}
void addage(int u,int v)
{
e[++js].u=u;e[js].v=v;
e[js].next=head[u];head[u]=js;
}
bool dfs(int u)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(!vis[v])
{
vis[v]=;
if(link[v]==- || dfs(link[v]))
{
link[v]=u;
return ;
}
}
}
return ;
}
int main()
{
while(scanf("%d",&n)==)
{
init();
for(int u,s,i=;i<n;i++)
{
scanf("%d:(%d)",&u,&s);
for(int v,j=;j<s;j++)
{
scanf("%d",&v);
addage(u,v);
addage(v,u);
}
}
int ans=;
for(int i=;i<n;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d\n",ans/);
}
return ;
}