匈牙利算法
算法思路
每次匹配的时候去访问已经匹配好的是否可以做出让步
AcWing 861. 二分图的最大匹配 原题链接
给定一个二分图，其中左半部包含n1n1个点（编号1~n1n1），右半部包含n2n2个点（编号1~n2n2），二分图共包含m条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1n1、 n2n2 和 mm。
接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1≤n1,n2≤5001≤n1,n2≤500, 1≤u≤n11≤u≤n1, 1≤v≤n21≤v≤n2, 1≤m≤1051≤m≤105
输入样例：
2 2 4
1 1
1 2
2 1
2 2
输出样例：
2
static int n1;
static int n2;
static int m;
static List<List<Integer>> graph = new ArrayList<>();
static int[] match;
static boolean[] st;
private static void add(int a, int b) {
graph.get(a).add(b);
}
private static boolean hungary(int x) {
List<Integer> list = graph.get(x);
for (int ii : list) {
// 对于每个单次匹配这个元素已经考虑过了，就不要重复考虑
if (!st[ii]) {
st[ii] = true;
// ii未匹配，或者 它匹配的元素 可以做出退让
if (match[ii] == 0 || hungary(match[ii])) {
match[ii] = x;
return true;
}
}
}
return false;
}
public static void main(String[] args) {
n1 = in.nextInt();
n2 = in.nextInt();
m = in.nextInt();
match = new int[n2 + 1];
st = new boolean[n2 + 1];
for (int i = 0; i < n1 + 1; i++) graph.add(new ArrayList<>());
for (int i = 0; i < m; i++) add(in.nextInt(), in.nextInt());
int res = 0;
//选择任意一个点集进行枚举
for (int i = 1; i <= n1; i++) {
Arrays.fill(st, false);
if (hungary(i)) res++;
}
out.println(res);
out.flush();
out.close();
}