算法背景

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。1955年，库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Kőnig)的一个定理构造了这个解法，故称为匈牙利算法 [1]

前置知识

什么是匹配、最大匹配？

匹配：

给定一个二分图GG，在GG的一个子图MM中，MM的边集E{E}中的任意两条边都不依附于同一个顶点，则称MM是一个匹配。[2]

也就是说，左右一一对应，任意两条边都没有公共顶点。

最大匹配：

一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。下图就是一个最大匹配，它包含 44条匹配边。

完美匹配：

若图中的一个匹配，包括了图中的所有点，则称这个匹配为完美匹配。完美匹配使图中所有点都为匹配点。上图就是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。

题目：httpss://www.acwing.com/problem/content/863/

给定一个二分图，其中左半部包含 n1n1 个点（编号1∼n1）（编号 1∼n_1），右半部包含 n2n2 个点编号1∼n2编号 1∼n_2，二分图共包含 mm 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

输入格式

第一行包含三个整数 n1n_1、 n2n_2 和 mm。

接下来 mm 行，每行包含两个整数 uu 和 vv，表示左半部点集中的点 uu 和右半部点集中的点 vv 之间存在一条边。

输出格式

输出一个整数，表示二分图的最大匹配数。

数据范围

1≤n1，n2≤500，1≤u≤n1，1≤v≤n2，1≤m≤1051≤n_1，n2≤500， 1≤u≤n_1， 1≤v≤n_2， 1≤m≤10^5

代码：

输入样例：

1
2
3
4
5
2 2 4
1 1
1 2
2 1
2 2

输出样例：

1
2
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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510, M = 1e5 + 10;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int x)
{
	for (int i = h[x]; ~i; i = ne[i])
	{
		int j = e[i];
		if (!st[j])
		{
			st[j] = true;
			if (match[j] == 0 || find(match[j]))
			{
				match[j] = x;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d%d%d", &n1, &n2, &m);
	
	memset(h , -1, sizeof h);
	while(m --)
	{
		int a, b;
		scanf("%d%d%d", &a, &b);
		add(a, b);
		
	}
	
	int res = 0;
	for (int i = 1; i <= n1; i++)
	{
		memset(st, false, sizeof st);
		if (find(i)) res ++;
	}
	printf("%d\n", res);

	return 0;
}
[1]
百度百科
[2]
百度百科