给定一个二分图，例如：
匈牙利算法能够快速的计算出一种匹配方式，使得匹配的数量最多。注意，一个成功的匹配方式中，没有两条边是共用了同一个点的。
形象的说，这个问题可以理解成二分图两边分别是男生和女生，有连线的表示可以凑成一对，匈牙利算法就是用来计算最多能够凑成多少对（不存在脚踏多条船的情况）。
例如左边是男生，右边是女生，可以任选一方为主动方，比如是男生方，那么流程如下。
对于每个男生结点，对所有与之有连线的女生结点，检查对应的女生是不是单身，如果是就直接凑成一对。那么在上图的例子中，前两个男生都可以直接匹配到自己连线的第一个女生：
对于男生 3 3 3而言，他所能匹配的第一个女生是 2 2 2，但是这个女生已经是非单身了。这个时候就要去不断尝试，尝试让女生 2 2 2已经匹配的男生 1 1 1换一个匹配的女生（而不会让当前已经成对的匹配数量减少）。
接下来男生
1
1
1检查自己所能匹配的下一个女生
4
4
4，这个女生是非单身，所以将男
1
1
1与女
4
4
4匹配，此时女
2
2
2被释放出来，得以和男
3
3
3匹配：
接下来检查下一个男生
4
4
4，它所能匹配的女生
3
3
3是单身，将他俩匹配：
至此，能匹配的都匹配上了，这个二分图的最大匹配数量是4。
求最大匹配的时候，可以直接存到邻接表里，因为遍历的时候是对每个男生遍历所有能匹配的女生，所以只要存一下从男生到女生的边，不需要像存普通无向图那样存双向边。
在实现时要注意，int match[]数组用来记录每个女生当前匹配的男生是哪一个（存标号），如果单身里面存的就是0。
由于在匈牙利算法中，即使一个女生已经有匹配了，也可能被更换匹配，所以还需要每次清空一个bool st[]数组，来记录当前给某个男生找匹配的过程中，每个女生有没有遍历过，防止出现死循环。
#include <iostream>
#include <cstring>
using namespace std;
// 由于只存单项，边M不用开两倍
const int N = 510, M = 1e5 + 10;
// 邻接表
int h[N], e[M], ne[M], idx;
void add_edge(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
// match记录女生当前匹配的男生
int match[N];
// st记录当前这轮每个女生有没有遍历过
// st[j] = true时候，j这个女生是被禁用的
bool st[N];
// 匈牙利算法，尝试给x找一个女朋友
bool find(int x) {
// 对于能够和x匹配的所有女生j
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
// 如果j没有被禁用（没有遍历过）
if (!st[j]) {
// 就将其锁定，因为要尝试让x匹配j
st[j] = true;
// 如果j本来就是单身，或者j的男朋友能换一个女朋友
if (match[j] == 0 || find(match[j])) {
// 就将x匹配上j
match[j] = x;
// 因为x能找到女朋友，所以返回true
return true;
}
}
}
// 尝试了x的所有能匹配的j都不行，就返回false
return false;
}
int main() {
// 读取二分图a->b
memset(h, -1, sizeof h);
int n1, n2, m;
cin >> n1 >> n2 >> m;
for (int i = 0; i < m; i ++ ) {
int a, b;
cin >> a >> b;
add_edge(a, b);
}
// 遍历每个男生尝试匹配
int res = 0;
for (int i = 1; i <= n1; i ++ ) {
memset(st, false, sizeof st);
// 每次尝试都会尝试让i匹配进来
// 结果res是只增不减的
if (find(i)) res ++ ;
}
cout << res << endl;
return 0;
}
特别要注意每轮要清空st数组，在这一轮中，尝试让女生j匹配给男生x时，就要设定st[j] = true以将j锁定了，被锁定的女生j永远不会解锁。
匈牙利算法基于贪心的思想，理论时间复杂度是多项式级别的 O ( n m ) O(nm) O(nm)，但是实际运行速度还是比较快的。
import java.util.*;
public class Main {
private static int h[], e[], ne[], idx;
private static void add_edge(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
private static int match[];
private static boolean st[];
private static boolean find(int x) {
for (int i = h[x]; i != -1; 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;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n1 = scanner.nextInt();
int n2 = scanner.nextInt();
int m = scanner.nextInt();
h = new int[n1 + 1];
for (int i = 1; i <= n1; i++)
h[i] = -1;
e = new int[m];
ne = new int[m];
for (int i = 0; i < m; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
add_edge(a, b);
}
match = new int[n2 + 1];
st = new boolean[n2 + 1];
int res = 0;
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++)
st[j] = false;
if (find(i))
res++;
}
System.out.println(res);
}
}