仔细看题目理解二分图的匹配是什么意思，最大匹配又是什么意思

题目

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

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

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

二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E}中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数

输入格式

第一行包含三个整数 n1、 n2 和 m

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

输出格式

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

数据范围

1≤n1,n2≤500
1≤u≤n1
1≤v≤n2
1≤m≤105

输入样例：

2 2 4
1 1
1 2
2 1
2 2

输出样例：

2

思路与代码

匈牙利算法其实就是男女互相怎么搭配，首先遍历男生去寻找搭配的女生，然后用dfs去看看意向女生有没有match的男生，如果有看看这个男生有没有备胎，有的话这个意向女生就会甩掉那个男生跟你在一起。她原本对象就会去跟备胎在一起，这是一个皆大欢喜的算法

这道题的思路：

1. 使用邻接表构建图。
2. 对于每个点进行匈牙利算法匹配，查看是否能找到增广路径。
3. 如果找到增广路径，则匹配数加一

import java.util.Arrays;
import java.util.Scanner;public class Main {static int n1, n2, m, N = 510, M = 200000, idx;static int[] ne = new int[M], e = new int[M], h = new int[M], match = new int[N];static boolean[] state = new boolean[N];// 添加一条边，构建邻接表public static void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}public static void main(String[] args) {Scanner in = new Scanner(System.in);n1 = in.nextInt();n2 = in.nextInt();m = in.nextInt();Arrays.fill(h, -1);// 构建图for (int i = 0; i < m; i++) {int a = in.nextInt();int b = in.nextInt();add(a, b);}int res = 0;// 遍历每个点，进行匈牙利算法匹配for (int i = 1; i <= n1; i++) {Arrays.fill(state, false);if (finds(i)) res++;}System.out.println(res);}// 匈牙利算法匹配private static boolean finds(int x) {for (int i = h[x]; i != -1; i = ne[i]) {int j = e[i];if (!state[j]) {state[j] = true;if (match[j] == 0 || finds(match[j])) {match[j] = x;return true;}}}return false;}
}

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替 路称为增广路（agumenting path）