UOJ 80：二分图最大权匹配 ← KM算法

【KM算法简介】
Kuhn-Munkres 算法，简称KM算法，是用于“二分图带权最大匹配问题”的经典算法。

【题目来源】
https://uoj.ac/problem/80

【题目描述】
从前一个和谐的班级，有 nl 个是男生，有 nr 个是女生。编号分别为 1, …… , nl 和 1, …… , nr。
有若干个这样的条件：第 v 个男生和第 u 个女生愿意结为配偶，且结为配偶后幸福程度为 w。
请问这个班级里幸福程度之和最大是多少？

【输入格式】
第一行三个正整数，nl,nr,m。
接下来 m 行，每行三个整数 v,u,w 表示第 v 个男生和第 u 个女生愿意结为配偶，且幸福程度为 w。保证 1≤v≤nl，1≤u≤nr，保证同一对 v,u 不会出现两次。

【输出格式】
第一行一个整数，表示幸福程度之和的最大值。
接下来一行 nl 个整数，描述一组最优方案。第 v 个整数表示 v 号男生的配偶的编号。如果 v 号男生没配偶请输出 0。

【输入样例】
2 2 3
1 1 100
1 2 1
2 1 1

【输出样例】
100
1 0

【限制与约定】
1≤nl,nr≤400，1≤m≤160000，1≤w≤10^9。

【算法分析】
Kuhn-Munkres 算法，简称KM算法，是用于“二分图带权最大匹配问题”的经典算法。
KM算法的经典模板题参见：https://blog.csdn.net/hnjzsyjyj/article/details/143027653

★ 学习KM算法之前，需先学习二分图匹配算法，如匈牙利算法。匈牙利算法的实现可参见：
https://blog.csdn.net/hnjzsyjyj/article/details/143020850
https://blog.csdn.net/hnjzsyjyj/article/details/143008866

★ KM算法基本概念
（1）顶标：给定二分图左部第 i 个结点的值为 lx[i]，右部第 j 个结点的值为 ly[j]，结点 i 到结点 j 的边权为 w[i][j]，把满足 lx[i]+ly[j]≥w[i][j] 的整数值 lx[i] 及 ly[j]，称为结点的顶标。
（2）二分图的相等子图：二分图中所有结点及满足 lx[i]+ly[j]=w[i][j] 的边构成的子图，称为二分图的相等子图。
（3）匹配：在图论中，一个“匹配”是一个边的集合，其中任意两条边都没有公共顶点。
（4）最大匹配：一个图的所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
（5）完备匹配：若二分图的某个匹配中，所有的顶点都是匹配点，那么这个匹配就是一个完备匹配。若相等子图中存在完备匹配，则这个完备匹配就是二分图的带权最大匹配。
（6）交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边、……，形成的路径叫交替路。
（7）增广路：从一个未匹配点出发，走交替路，如果途经另一个未匹配点（出发点不算），则这条交替路称为增广路（agumenting path）。

★ KM算法的基本思想
对任意 i，j， 在满足 lx[i]+ly[j]≥w[i][j] 的前提下，给每个结点随意赋值一个顶标， 然后采取适当策略不断扩大相等子图的规模，直至相等子图存在完备匹配。
Kuhn－Munkres算法流程：
（1）初始化可行顶标的值。通常，lx[i] 取输入各值的最大值，ly[j] 取 0。
（2）用匈牙利算法寻找完备匹配；
（3）若未找到完备匹配则修改可行顶标的值；
（4）重复（2）和（3），直到找到相等子图的完备匹配为止。

【算法代码】

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

typedef long long LL;
const int inf=0x3f3f3f3f;
const int maxn=405;

/* If get a perfect match for maximum weight,
 we set the edge weight to -inf. Otherwise,
 Compare which is greater, edge weight or 0. Get it. */
LL mp[maxn][maxn]; //edge weight
LL lx[maxn],ly[maxn]; //Topmark
LL slack[maxn];
bool visx[maxn],visy[maxn];
int boy[maxn],girl[maxn];
int p[maxn]; //pre
int q[maxn];
int head,tail;
int N;

bool check(int v) {
    visy[v]=true;
    if(boy[v]) {
        visx[boy[v]]=true;
        q[tail++]=boy[v];
        return false;
    }
    while(v) {
        boy[v]=p[v];
        swap(v,girl[p[v]]);
    }
    return true;
}

void bfs(int x) {
    memset(q,0,sizeof(q));
    head=tail=0;
    q[tail++]=x;
    visx[x]=true;
    while(1) {
        while(head!=tail) {
            int x=q[head++];
            for(int y=1; y<=N; y++) {
                if(!visy[y]) {
                    LL d=lx[x]+ly[y]-mp[x][y];
                    if(d<slack[y]) {
                        p[y]=x;
                        slack[y]=d;
                        if(!slack[y] && check(y))
                            return;
                    }
                }
            }
        }

        LL d=inf;
        for(int i=1; i<=N; i++)
            if(!visy[i]) d=min(d,slack[i]);

        for(int i=1; i<=N; i++) {
            if(visx[i]) lx[i]-=d;
            if(visy[i]) ly[i]+=d;
            else slack[i]-=d;
        }

        for(int i=1; i<=N; i++)
            if(!visy[i] && !slack[i] && check(i))
                return;
    }
}

LL km() {
    for(int i=1; i<=N; i++) {
        lx[i]=-inf;
        ly[i]=0;
        for(int j=1; j<=N; j++)
            lx[i]=max(lx[i],mp[i][j]);
    }

    for(int i=1; i<=N; i++) {
        memset(slack,inf,sizeof(slack));
        memset(visx,0,sizeof(visx));
        memset(visy,0,sizeof(visy));
        bfs(i);
    }

    LL ans=0;
    for(int i=1; i<=N; i++) {
        ans+=mp[i][girl[i]];
    }

    return ans;
}

int main() {
    int nl,nr,m;
    cin>>nl>>nr>>m;
    N=max(nl,nr);
    while(m--) {
        int u,v,w;
        scanf("%d%d%d", &u, &v, &w);
        mp[u][v]=max(w,0);
    }
    cout<<km()<<endl;

    for(int i=1; i<=nl; i++) {
        if(i>1) cout<<" ";
        if(mp[i][girl[i]]>0) cout<<girl[i];
        else cout<<"0";
    }
    cout<<endl;

    return 0;
}

/*
in:
2 2 3
1 1 100
1 2 1
2 1 1

out:
100
1 0
*/

【参考文献】
https://www.cnblogs.com/huyufeifei/p/10350763.html
https://blog.csdn.net/birdmanqin/article/details/90272134
https://uoj.ac/submission/472960
https://www.cnblogs.com/wenruo/p/5264235.html
https://blog.csdn.net/iteye_4729/article/details/82369926
https://blog.csdn.net/u011815404/article/details/84855464
https://blog.csdn.net/challengerrumble/article/details/50572817
https://blog.csdn.net/guhaiteng/article/details/52556591
https://blog.csdn.net/EQUINOX1/article/details/135611059
https://www.acwing.com/file_system/file/content/whole/index/content/2794583/
https://blog.sengxian.com/algorithms/km
https://oi-wiki.org/graph/graph-matching/bigraph-weight-match/
https://www.acwing.com/solution/content/5334/
https://blog.csdn.net/zack_liu/article/details/123396889
https://www.cnblogs.com/huyufeifei/p/10350763.html