自动搬运

查看原文

来自洛谷，原作者为

	tjtdrxxz 要是把博士抬去寝室，会不会被人误会啊？干脆就这样子放着好了......？

搬运于2025-08-24 23:02:42，当前版本为作者最后更新于2024-09-15 09:45:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：二分图

二分图是长这样滴： 一眼就能看出二分图类似于男女关系，A 喜欢 B，但 B 不一定喜欢 A，但 B 喜欢的人不一定喜欢 B。所以我们需要委屈下男方。如果有一对匹配好的男女（A 和 B），但又有另一个人（C）喜欢女方，我们就先把 C 和 B 连成一对，然后就看 A 能不能和别的女生匹配，类似这样：

本题思路

我们可以把每行每列都看成一个点，一辆车占据每行每列就相当于占据他所在的行和列代表的点。

那么为了找到最多的车，自然就是二分图最大匹配了。

这题的数据范围比较小，$N, M \le 200$，所以 $O (n^2)$ 可以过。

code:

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	register char in = getchar(),f = 0; register int t = 0;
	for(;in < '0' || in > '9';in = getchar())if(!(in ^ 45))f = 1;
	for(;in >= '0' && in <= '9';in = getchar())
	 t = (t << 1) + (t << 3) + (in ^ 48);
	return f ? -t : t;
}
void write(register long long x)
{
	static int t[25];register int tp = 0;
	if(x == 0)return(void)(putchar('0'));
	else if(x < 0) putchar('-'),x = -x;
	while(x) t[tp++] = x % 10,x /= 10;
	while(tp--) putchar(t[tp] + 48);
}
#define stdi stdin
#define stdo stdout
int n = read(),m = read(),t = read();
int vis[1012][1012],ans,dis[100012];
int lk[100012];
inline short dfs(int u)
{
	for(int i = 1;i <= m;i++)
	{
		if(!vis[u][i] && !dis[i])
		{
			dis[i] = 1;
			if(!lk[i] || dfs(lk[i]))
			{
				lk[i] = u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	setvbuf(stdi,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
	setvbuf(stdo,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
	for(int i = 1;i <= t;i++)
	{
		register int u = read();
		register int v = read();
		vis[u][v] = 1;
	}
	for(int i = 1;i <= n;i++)
	{
		memset(dis,0,sizeof(dis));
		if(dfs(i)) ans++;
	}
	write(ans),puts("");
}