Acwing861. 二分图的最大匹配（匈牙利算法）

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

题目

给定一个二分图，其中左半部包含 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）