1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

//luogu3386 二分图匹配 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1003;

int n,m,e;
bool d[maxn][maxn];
void input()
{
	scanf("%d%d%d",&n,&m,&e);
	for(int i=1;i<=e;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(y<=m)
			d[x][y]=true;
	}
}
int match[maxn];
bool used[maxn];
bool findPath(int k)
{
	for(int i=1;i<=m;++i)
	{
		if(d[k][i]&&!used[i])
		{
			used[i]=true;
			if((!match[i])||findPath(match[i]))
			{
				match[i]=k;
				return true;
			}
		}
	}
	return false;
}
int ans=0;
void Edmonds()
{
	for(int i=1;i<=n;++i)
	{
		memset(used,0,sizeof(used));
		if(findPath(i))
			++ans;
	}
}
int main()
{
	freopen("luogu3386_1.in","r",stdin);
	//freopen("luogu3386.out","w",stdout);
	input();
	Edmonds();
	printf("%d\n",ans);
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

/*
	poj1274
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
template<typename T>
bool read(T& w)
{
	char r;
	for(r=getchar();(r<48||r>57)&&r!=-1;r=getchar());
	if(r==-1)return false;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	return true;
}
const int maxn=303;
const int maxm=303;
int n,m;
struct EDGE
{
	int to,nxt;
	void init(int too,int nxtt)
	{
		to=too,nxt=nxtt;
	}
}edge[maxn*maxm];
int ek=0;
int node[maxn];
inline void addEdge(int from,int too)
{
	edge[++ek].init(too,node[from]);
	node[from]=ek;
}

void input()
{
	memset(node+1,0,n*sizeof(int));
	ek=0;
	int s,x;
	for(int i=1;i<=n;++i)
	{
		read(s);
		for(int j=1;j<=s;++j)
		{
			read(x);
			addEdge(i,x);
		}
	}
}

int match[maxm];
bool used[maxm];
bool findPath(int k)
{
	for(int i=node[k];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(!used[v])
		{
			used[v]=true;
			if(match[v]==0||findPath(match[v]))//如果还未安排或者可以腾出 
			{
				match[v]=k;
				return true;
			}
		}
	}
	return false;
}
int ans=0;
void solve()
{
	memset(match+1,0,m*sizeof(int));
	ans=0;
	for(int i=1;i<=n;++i)
	{
		memset(used+1,0,m*sizeof(bool));
		if(findPath(i))++ans;
	}
}

int main()
{
	freopen("poj1274_1.in","r",stdin);
	//freopen("poj1274.out","w",stdout);
	while(read(n),read(m))
	{
		input();
		solve();
		printf("%d\n",ans);
	}
	return 0;
}