题解：P3386 【模板】二分图最大匹配

PCSJZ · 2025-05-14 12:41:47 · 题解

匈牙利算法

我们用一个二维数组来存图，然后遍历 n 个节点，看看这 n 个点中，有多少个可以连。

核心代码

bool dfs(int u) {
    for (int i = 1; i <= m; i++) {
        if (f[u][i] && !vis[i]) {
            vis[i] = 1;
            if (!match[i] || dfs(match[i])) {
                match[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

遍历 m 条边，看看那些边跟 u 联系上了，接着看当前节点有没有被连上，如果没有，更新访问数组。接下来看当前节点的匹配节点是什么，如果没有，那么把匹配节点设成 u；如果有，尝试把它连得点断掉，把当前节点匹配上 u。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>

using namespace std;

const int N = 1e3;
bool f[N][N];
bool vis[N];
int match[N], n, m, e; 

bool dfs(int u) {
    for (int i = 1; i <= m; i++) {
        if (f[u][i] && !vis[i]) {
            vis[i] = 1;
            if (!match[i] || dfs(match[i])) {
                match[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d%d%d", &n, &m, &e);
    for (int i = 1; i <= e; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        f[x][y] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}