poj 1274 The Perfect Stall （匈牙利算法）

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年05月25日 星期三 17时49分22秒
  4File Name :code/poj/1274.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=405;
 34int n,m;
 35int head[N];
 36int cnt;
 37int link[N];
 38bool vis[N];
 39struct Edge
 40{
 41    int v;
 42    int nxt;
 43}edge[N*N];
 44void addedge(int u,int v)
 45{
 46    edge[cnt].v = v;
 47    edge[cnt].nxt = head[u];
 48    head[u] = cnt;
 49    cnt++;
 50}
 51
 52bool dfs( int u)
 53{
 54  //  cout<<"u:"<<u<<endl;
 55    for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
 56    {
 57	int v = edge[i].v;
 58//	cout<<"v:"<<v<<endl;
 59	if (vis[v]) continue;
 60	vis[v] = true;
 61
 62	if (link[v]==-1||dfs(link[v]))
 63	{
 64	    link[v] = u;
 65	    return true;
 66	}
 67    }
 68    return false;
 69}
 70int hung()
 71{
 72    int res = 0 ;
 73    ms(link,-1);
 74    for ( int i = 1 ; i <= n ; i++)
 75    {
 76	ms(vis,false);
 77	if (dfs(i)) res++;
 78    }
 79
 80    return res;
 81}
 82int main()
 83{
 84	#ifndef  ONLINE_JUDGE 
 85	freopen("code/in.txt","r",stdin);
 86  #endif
 87
 88	while (scanf("%d%d",&n,&m)!=EOF)
 89	{
 90	    ms(head,-1);
 91	    cnt = 0 ;
 92
 93	    for ( int i = 1 ; i <= n ; i++)
 94	    {
 95		int num;
 96		scanf("%d",&num);
 97		while (num--)
 98		{
 99		    int x;
100		    scanf("%d",&x);
101		    x = x + n;
102		    addedge(i,x);
103		}
104	    }
105	    int ans = hung();
106	    printf("%d\n",ans);
107	}
108
109  #ifndef ONLINE_JUDGE  
110  fclose(stdin);
111  #endif
112    return 0;
113}