记录编号	107986	评测结果	AAAAAAAAA
题目名称	[USACO 4.2] 完美的牛栏	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2014-07-01 20:16:30	内存使用	1.13 MiB

/*
网络流练习
by Raywzy
*/
#include<fstream>
#include<queue>
#include<cstring>
#include<cmath>
#include<deque>
using namespace std;
ifstream fin("stall4.in");
ofstream fout("stall4.out");
deque<int>Q;
const int INF=99999999;
int map[500][500];
int Pre[500];//记录前驱,同时令源点为0，汇点为N+M+1
int N,M,temp;
int MinFlow=INF;
int MaxFlow=0;
bool BFS(int src,int des)
{
	memset(Pre,-1,sizeof(Pre));//初始化前驱数组
	int i,temp;
	Q.clear();
	Q.push_back(src);
	while(!Q.empty())
	{
		temp=Q.at(0);
		Q.pop_front();
		for(i=0;i<=N+M+1;i++)
		{
			if(map[temp][i]>0&&Pre[i]==-1)
			{
				Q.push_back(i);
				Pre[i]=temp;
				if(i==des)
					return 1;
			}
		}
	}
	return 0;
}
int Solve()
{
	int i;
	while(BFS(0,N+M+1))//当有增广路时
	{
		MinFlow=INF;
		for(i=N+M+1;i!=0;i=Pre[i])
			MinFlow=min(MinFlow,map[Pre[i]][i]);//求出当前可以增加的流量
		//更新残余网络
		for(i=N+M+1;i!=0;i=Pre[i])
		{
			map[Pre[i]][i]-=MinFlow;
			map[i][Pre[i]]+=MinFlow;
		}
		MaxFlow+=MinFlow;
	}
	return MaxFlow;
}
int main()
{
	fin>>N>>M;
	int i,n,j;
	for(i=1;i<=N;i++)
	{
		fin>>n;
		for(j=1;j<=n;j++)
		{
			fin>>temp;
			map[i][temp+N]=1;
		}
	}
	//开始建立超级源点与超级汇点
	for(i=1;i<=N;i++)
		map[0][i]=1;
	for(i=N+1;i<=N+M;i++)
		map[i][N+M+1]=1;
	fout<<Solve()<<endl;
	return 0;
}