boj 342

Description
xiaoming实在太好管闲事了.有一天他去参加一个舞会,这里聚集了一大堆帅哥美女,但是舞会却不是那么顺利,虽然帅哥和美女的人数都是相同的,但并不是每一位帅哥都能找到他的舞伴,原因就是有些女生只愿意接受某些男生的邀请.小明为了舞会的顺利进行,xiaoming只好厚着脸皮去和这些女生搭话,了解到了这些女生就都愿意接受哪些男生的邀请,那么剩下的工作就是要小明给这些帅哥美女们搭搭线,小明只希望能找到舞伴的人尽量多.

Input
多组数据测试 
每行一个偶数n(n<=1000) ，表示参加舞会的人数，其中男生和女生一样多。
接下来n/2行，每一行先是一个正整数m,然后是m个整数a1,a2…..am(ai<=n/2).
其中第i行表示，第i个女生只愿意接受m个男生的邀请，这分别是第a1,a2….am号男生


Output
在xiaoming的努力下，最多能有多少人找到自己的舞伴

Sample Input

8
1 3
2 2 4
1 2
1 2


Sample Output

6


Hint
一种组合方案是：1号女生和3号男生，2号女生和4号男生，3号女生和2号男生，那么只有4号女生和1号男生没有找到舞伴。

Source
Xiaoming@Fourth

思路：

二分图最大匹配，刚学会，理解不是很深入

相关知识：

http://www.cnblogs.com/pony1993/archive/2012/07/25/2607738.html

http://www.matrix67.com/blog/archives/39

http://imlazy.ycool.com/post.1603708.html

代码：

#include<iostream>
using namespace std;
#define N 505
int map[N][N],n1,n2,visit[N],Link[N];
int findroad(int x)
{
	for(int i=1;i<=n2;i++)
	{
		if(map[x][i]&&!visit[i])
		{
			visit[i] = 1;
			if(Link[i]==0||findroad(Link[i]))//x到i可到达，且增广路径上不存在重复点
			{
				Link[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int n,ans;
	while(~scanf("%d",&n))
	{
		memset(map,0,sizeof(map));
		memset(Link,0,sizeof(Link));
		ans = 0;
		n1 = n2 = n/2;
		for(int i=1;i<=n1;i++)
		{
			int num,a;
			scanf("%d",&num);
			for(int j=0;j<num;j++)
			{
				scanf("%d",&a);
				map[i][a] = 1;
			}
		}
		for(int i=1;i<=n1;i++)
		{
			memset(visit,0,sizeof(visit));
			if(findroad(i))
				ans++;
		}
		printf("%d\n",2*ans);
	}
}