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);}
}