#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define CLR(x) memset(x,0,sizeof(x))
#define __CLR(x) memset(x,-1,sizeof(x))
using namespace std;
vector<int>G[1510];
bool vis[1510];
int match[1510];
bool dfs(int u)
{
for(int i=0;i<G[u].size();i++)
{
int t=G[u][i];
if(!vis[t])
{
vis[t]=1;
if(match[t]==-1||dfs(match[t]))
{
match[t]=u;
return true;
}
}
}
return false;
}
int main()
{
//ios_base::sync_with_stdio(0);
int n;
while(~scanf("%d",&n))
{
for(int i=0; i<n; i++)
{
int m,k;
scanf("%d:(%d)",&m,&k);
for(int j=0; j<k; j++)
{
int a;
scanf("%d",&a);
G[m].push_back(a);
G[a].push_back(m);
}
}
int res=0;
__CLR(match);
for(int i=0; i<n; i++)
{
CLR(vis);
if(dfs(i))
res++;
}
printf("%d\n",res/2);
for(int i=0;i<1510;i++)
G[i].clear();
}
}
源代码：https://blog.csdn.net/u012294939/article/details/43741775
解释：
1、利用动态开点来储存边，
即u-v的边用a[u][v]表示，（加入的话：a[u].push_back[v];）
2、匈牙利算法的理论应用，最小顶点覆盖数=最大匹配数
3、本题是树状结构的无向无环图（区别于有向无环图），所以会进行补全操作，所以会产生两倍的匹配数目，结果要除2，如果是有向无环图，那么就直接输出就行了
4、本题目的起始位置是0，中止位置是n-1，所以match数组（最大匹配数的匹配对象数组）要初始化为-1
5、关于动态数组a的元素的解释和下标：
第一部分：输入部分：每开一个新的点，就将下标加一，然后将边结点放入。
第二部分：匹配函数部分：范围是由0~sizeof（a[x]）与之相连的每一条边的节点都被遍历，
即 t = G [x] [i] 是一个节点的编号，而不是（下标或者等于布尔型）。
6.没了
