gistfile1.cpp

#include <fstream>
using namespace std;
int N,M;
int capacity[410][410];
class node
{
public:
	int n;
	int pre;
};
node queue[410];
int q_size;
bool visit[410];
bool BFS()//get to end
{

	for (int i = 0 ; i<=N+M+1; i++)
	{
		visit[i] = false;
	}
	q_size = 0;
	queue[q_size].n = 0;
	visit[0] = true;
	queue[q_size].pre = -1;

	q_size++;
	for ( int i = 0 ; i<q_size; i++ )
	{
		for (int k = 0; k<=N+M+1; k++)
		{
			if (capacity[queue[i].n][k]>0&&visit[k]==false)//set visit!!
			{
				queue[q_size].n = k;
				visit[k] = true;
				queue[q_size].pre = i;
				q_size++;
				if (k==M+N+1)  return true;
			}
		}
	}
	return false;
}
int main()
{
	ifstream fin("stall4.in");
	ofstream fout("stall4.out");
	fin>>N>>M;
	for (int i = 1; i<=N; i++)
	{
		int num,kk;
		fin>>num;
		for (int k = 0;k<num;k++)
		{
			fin>>kk;
			capacity[i][N+kk] = 1;
		}
	}
	//source
	for (int i = 1;i<=N ;i++)
	{
		capacity[0][i] = 1;
	}
	//sink
	for (int i = N+1;i<=N+M;i++)
	{
		capacity[i][N+M+1] = 1;
	}



	//get the path in the queue :0-q_size-1
	int max_flow = 0;
	while(BFS())
	{
		//find the min capacity along the path
		int min_capacity = 0x7fffffff;
		int i = q_size-1; 
		while (queue[i].pre!=-1)
		{
			if(capacity[queue[queue[i].pre].n][queue[i].n]<min_capacity)
				min_capacity = capacity[queue[queue[i].pre].n][queue[i].n];
			i = queue[i].pre;
		}
		//augment the path
		max_flow += min_capacity;

		i = q_size-1;
		while (queue[i].pre!=-1)
		{

			capacity[queue[queue[i].pre].n][queue[i].n] -= min_capacity;
			capacity[queue[i].n][queue[queue[i].pre].n] += min_capacity;
			i = queue[i].pre;
		}

	}
	fout<<max_flow<<endl;


	fin.close();
	fout.close();
	return 0;
}