算法记录-7-（二分图带权最大匹配-KM算法）

时间复杂度：O（N^4）
本算法局限性较大，只能在满足“带权最大匹配一定是完备匹配”的图中正确求解，所以一般使用费用流来求解此类问题，但是本算法在求解稠密图时效率要高于费用流

const int N=105;
int w[N][N];
int la[N],lb[N];
bool va[N],vb[N];
int match[N];
int n,delta,upd[N];
bool dfs(int x){
    va[x]=1;
    for(int y=1;y<=n;y++)
        if(!vb[y])
            if(la[x]+lb[y]-w[x][y]==0){
                vb[y]=1;
                if(!match[y]||dfs(match[y])){
                    match[y]=x;
                    return true;
                }
            }
            else upd[y]=min(upd[y],la[x]+lb[y]-w[x][y]);
    return false;
}
int KM(){
    for(int i=1;i<=n;i++){
        la[i]=-(1<<30);
        lb[i]=0;
        for(int j=1;j<=n;j++)
            la[i]=max(la[i],w[i][j]);
    }
    for(int i=1;i<=n;i++)
        while(true){
            memset(va,0,sizeof va);
            memset(vb,0,sizeof vb);
            for(int j=1;j<=n;j++)    upd[j]=1e10;
            if(dfs(i))    break;
            for(int j=1;j<=n;j++)
                if(!vb[j])    delta=min(delta,upd[j]);
            for(int j=1;j<=n;j++){
                if(va[j])    la[j]-=delta;
                if(vb[j])    lb[j]+=delta;
            }
            int ans=0;
            for(int i=1;i<=n;i++)    ans+=w[match[i]][i];
            return ans;
        }
}