记录编号	270636	评测结果	AAAAAAAAA
题目名称	[USACO 4.2] 完美的牛栏	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-06-15 09:34:27	内存使用	0.00 MiB

//求二分图最大匹配的匈牙利算法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210;
struct edge{
	int to;
	edge* prev;
	edge():to(0),prev(NULL){}
}ee[2*maxn*maxn];
void insert(int,int);
bool path(int);
int maxmatch();
int len=0;
edge* last[maxn]={NULL};
int na,nb;//a集合和b集合中顶点的个数
int ca[maxn]={0},cb[maxn]={0};//用来记录匹配的元素是哪个
bool vis[maxn];
int x,y;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("stall4.in","r",stdin);
	freopen("stall4.out","w",stdout);
#endif
	scanf("%d%d",&na,&nb);
	for(int i=1;i<=na;i++){
		scanf("%d",&x);
		for(int j=0;j<x;j++){
			scanf("%d",&y);
			insert(i,y);
		}
	}
	printf("%d",maxmatch());
	return 0;
}
inline void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
inline bool path(int x){//找增广路
	for(edge* e=last[x];e;e=e->prev){
		int y=e->to;
		if(!vis[y]){
			vis[y]=true;
			if(!cb[y]||path(cb[y])){
				//如果y集合中的v元素没有匹配或者是v已经匹配，
				//但是从cy[v]中能够找到一条增广路
				ca[x]=y;
				cb[y]=x;//找到增广路，修改匹配M
				return true;
			}
		}
	}
	return false;
}
inline int maxmatch(){//求最大匹配
	int result=0;
	for(int i=1;i<=na;i++){
		if(!ca[i]){//还没被匹配
			memset(vis,0,sizeof(vis));
			result+=path(i);//以i为起点开始查找增广路，若返回true，匹配数+1
		}
	}
	return result;
}
int haha=MAIN();
int main(){;}