匈牙利算法

算法：匈牙利算法
问题：二分图最大匹配问题
输入：二分图
输出：最大匹配的值、匹配方案
备注： $O(|V||E|)$

#include<bits/stdc++.h>
using namespace std;
const int maxn=500+1;
const int maxm=500+1;

// data structure
int L[maxn][maxm];

void add_edge(int x,int y){
    L[x][y]=1;
}

// hungary's resources
int n; // amount of girls
int m; // amount of boys
int match[maxm], used[maxm];

int find(int x){
    for(int y=1;y<=m;y++){
        if(L[x][y]&&!used[y]){
            used[y]=1;
            if(!match[y]||find(match[y])){
                match[y]=x;
                return 1;
            }
        }
    }
    return 0;
}

int hungary(){
    for(int y=1;y<=m;y++)
        match[y]=0;
    int ans=0;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++)
            used[y]=0;
        if(find(x)) ans++;
    }
    return ans;
}


int main(){
    int k; // amount of edges
    scanf("%d%d%d",&k,&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            L[i][j]=0;
    int x,y;
    for(int i=1;i<=k;i++){
        scanf("%d%d",&x,&y);
        add_edge(x,y);
    }

    int ans=hungary();
    printf("%d\n",ans);
    return 0;
}

参考资料：https://www.cnblogs.com/cruelty_angel/p/10808729.html