算法板子
算法板子

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 3e5 + 5;
int h[N], ver[M], ne[M], idx;
int u[N];
int n1, n2, m;
int vis[N], match[N];
int res;
void add(int x, int y) {
    ver[++idx] = y;
    ne[idx] = h[x];
    h[x] = idx;
}
bool dfs(int x) {
    for (int i = h[x], y; i != -1; i = ne[i]) {
        if (!vis[y = ver[i]]) {
            vis[y] = 1;
            if (!match[y] || dfs(match[y])) {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for (int i = 1; i <= n1; ++i) {
        memset(vis, 0, sizeof vis);
        if (dfs(i)) ++res;
    }
    cout << res << endl;
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/maximum-match-in-bi-graph-by-hungary-algorithm/
最后修改日期:2020年8月25日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。