二分图最大匹配

• OI Wiki: https://oi-wiki.org/graph/graph-matching/bigraph-match/

题目	难度
$1820. 最多邀请的个数	中等

增广路算法 Augmenting Path Algorithm

假设图有 n 个顶点，m 条边。

时间复杂度：O(nm)。

1820. 最多邀请的个数

import java.util.Arrays;

public class Solution1820 {
    private int[][] g;
    private int m, n, dfn;
    private int[] pa, pb, vis;

    public int maximumInvitations(int[][] grid) {
        this.g = grid;
        m = grid.length;
        n = grid[0].length;
        dfn = 0;
        pa = new int[m];
        Arrays.fill(pa, -1);
        pb = new int[n];
        Arrays.fill(pb, -1);
        vis = new int[m];

        int res = 0;
        while (true) {
            dfn++;
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                if (pa[i] == -1 && dfs(i)) {
                    cnt++;
                }
            }
            if (cnt == 0) {
                break;
            }
            res += cnt;
        }
        return res;
    }

    private boolean dfs(int x) {
        vis[x] = dfn;
        for (int y = 0; y < n; y++) {
            if (g[x][y] == 0) continue;
            if (pb[y] == -1) {
                pb[y] = x;
                pa[x] = y;
                return true;
            }
        }
        for (int y = 0; y < n; y++) {
            if (g[x][y] == 0) continue;
            if (vis[pb[y]] != dfn && dfs(pb[y])) {
                pa[x] = y;
                pb[y] = x;
                return true;
            }
        }
        return false;
    }
}

（全文完）