KM算法

问题：二分图最大权匹配问题
输入：（具有完美匹配的）二分图
输出：最大权匹配的值、匹配方案
备注：复杂度

#include<bits/stdc++.h>
using namespace std;
const int maxn=300+1;
const int INF=0x7fffffff;
typedef long long LL;

// data structure
int w[maxn][maxn];

// KM's resources
int n; // size of X and Y
int slack; // slack of Y
int lx[maxn], ly[maxn];
int match[maxn], visx[maxn], visy[maxn];

int find(int x){
    visx[x]=true;
    for(int y=1;y<=n;y++){
        if(visy[y]) continue;
        int t=lx[x]+ly[y]-w[x][y];
        if(!t){
            visy[y]=true;
            if(!match[y]||find(match[y])){
                match[y]=x;
                return true;
            }
        }
        else{
            slack=min(slack,t);
        }
    }
    return false;
}

 LL km(){
    for(int i=1;i<=n;i++)
        lx[i]=ly[i]=match[i]=0;
    for(int x=1;x<=n;x++)
        for(int y=1;y<=n;y++)
            lx[x]=max(lx[x],w[x][y]);

    for(int x=1;x<=n;x++){
        for(;;){
            for(int i=1;i<=n;i++)
                visx[i]=visy[i]=false;
            slack=INF;
            if(find(x)) break;
            for(int i=1;i<=n;i++){
                if(visx[i]) lx[i] -= slack;
                if(visy[i]) ly[i] += slack;
            }
        }
    }

    LL ans=0;
    for(int y=1;y<=n;y++){
        int x=match[y];
        ans+=w[x][y];
    }
    return ans;
}


int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d", &w[i][j]);
        }
    }
    LL ans=km();
    printf("%lld\n",ans);
    return 0;
}

参考资料：https://www.cnblogs.com/kuangbin/p/3228861.html