$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

匈牙利算法可以求出二分图的最大匹配。

对于左边的每个点从前往后看。

• 如果无法匹配，就放弃。
• 否则不断让之前的匹配反悔。

匈牙利算法准则：待嫁闺中，据为己有；名花有主，求他放手。

时间复杂度最坏 $O(nm)$，实际远小于最坏复杂度。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 515, M = 1e5 + 15;
int n1, n2, m;
int h[N], e[M], ne[M], idx = 0;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int ans = 0;
int match[N];
bool st[N];

int dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) { //枚举每个右部点
        int v = e[i];
        if (st[v]) continue;
        st[v] = 1;
        if (!match[v] || dfs(match[v])) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

int main() {
    scanf("%d%d%d", &n1, &n2, &m);
    for (int i = 1; i <= max(n1, n2); i++) h[i] = -1;
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    for (int i = 1; i <= n1; i++) { //考虑每一个左部点
        for (int j = 1; j <= n2; j++) st[j] = 0;
        if (dfs(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}