裸的匈牙利。
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}