备战NOIP——模板复习13

这里只有模板，并不作讲解，仅为路过的各位做一个参考以及用做自己复习的资料，转载注明出处。

二分图匹配

匈牙利算法

/*Copyright: Copyright (c) 2018
*Created on 2018-11-02  
*Author: 十甫
*Version 1.0 
*Title: 匈牙利算法
*Time: inf mins
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 10005;
const int maxm = 100005;

int to[maxn][maxn], n, m, e;
int matchx[maxn], matchy[maxn];
bool vis[maxn];
bool dfs(int u) {
    for(int v = n + 1;v <= n + m;v++) if(to[u][v]) {
        if(vis[v]) continue;
        vis[v] = true;
        if(!matchy[v] || dfs(matchy[v])) {
            matchx[u] = v, matchy[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d%d%d", &n, &m, &e);
    for(int i = 1;i <= e;i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if(a < 1 || a > n || b < 1 || b > m) continue;
        to[a][b + n] = to[b + n][a] = true;
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) {
        if(!matchx[i]) {
            memset(vis, false, sizeof(vis));
            ans += dfs(i);
        }
    }
    printf("%d\n", ans);
    return 0;
}