匈牙利算法模板

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, M = 1e5 + 10;

int n, m, e;
int head[N], ed[M], ne[M], idx;
int match[N];
bool vis[N];

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

bool dfs(int u) {
   
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (!vis[v]) {
   
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
   
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m >> e;
    for (int i = 0; i < e; ++i) {
   
        int u, v;
        cin >> u >> v;
        v = n + v;
        add(u, v);
    }

    memset(match, -1, sizeof match);

    //枚举左侧的点
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
   
        if (match[i] == -1) {
   
            memset(vis, false, sizeof vis);
            if (dfs(i)) ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}