二分图的最大匹配 匈牙利算法 模板

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

const int N = 505, M = 100005;

int n1, n2, m;

int head[N], cnt;

struct {
   
    int to, nxt;
}edges[M];

bool st[N];     //记录右半部分节点是否被匹配
int match[N];   //记录右半部分匹配的左半部分节点编号

void add(int a, int b)
{
   
    edges[++cnt].to = b;
    edges[cnt].nxt = head[a];
    head[a] = cnt; 
}

int find(int x)
{
   
    for (int e = head[x]; e != 0; e = edges[e].nxt) {
   
        int to = edges[e].to;
        if (!st[to]) {
   
            st[to] = true;

            if (match[to] == 0 or find(match[to])) {
   
                match[to] = x;
                return true;
            }
        }
    }

    return false;
}

int main() 
{
   
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n1 >> n2 >> m;

    for (int i = 0; i < m; ++i) {
   
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    int res = 0;

    for (int i = 1; i <= n1; ++i) {
   
        memset(st, 0, sizeof st);
        if (find(i))
            res++;
    }

    cout << res;

    fclose(stdin);
    fclose(stdout);
    return 0;
}