图论：二分图最大权匹配KM算法

洛谷P6577 【模板】二分图最大权完美匹配

点击查看代码块

/*
Kuhn－Munkres
复杂度O(n^3)，加入松弛操作
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1010;
const int inf = 0x7f7f7f7f;
const ll inf_ll = 1ll*inf*inf;
typedef long long ll;
int n,m;
struct KM{
    ll mp[maxn][maxn];
    int link_x[maxn], link_y[maxn], N;//邻接矩阵存图,左边点的匹配点,右边点的匹配点,两边点中的最大点数个数+1
    bool visx[maxn], visy[maxn];
    int que[maxn << 1], top, fail, pre[maxn];//手写队列
    ll hx[maxn], hy[maxn], slk[maxn];//左边点顶标，右边点顶标，松弛操作
    int check(int x){
        visx[x] =true;
        if(link_x[x]){
            que[fail++] = link_x[x];
            return visy[link_x[x]] = true;
        }
        while(x){
            link_x[x] = pre[x];
            swap(x, link_y[pre[x]]);
        }
        return 0;
    }
    void bfs(int S){
        for(int i=1; i<=N; i++){
            slk[i] = inf_ll;
            visx[i] = visy[i] = false;
        }
        top = 0; fail = 1;
        que[0] = S;
        visy[S] = true;
        while(1){
            ll d;
            while(top < fail){
                for(int i = 1, j = que[top++]; i <= N; i++){
                    if(!visx[i] && slk[i] >= (d = hx[i] + hy[j] - mp[i][j])){
                        pre[i] = j;
                        if(d) slk[i] = d;
                        else if(!check(i)) return;
                    }
                }
            }
            d = inf_ll;
            for(int i=1; i<=N; i++){
                if(!visx[i] && d > slk[i]) d = slk[i];
            }
            for(int i=1; i<=N; i++){
                if(visx[i]) hx[i] += d;
                else slk[i] -= d;
                if(visy[i]) hy[i] -= d;
            }
            for(int i=1; i<=N; i++){
                if(!visx[i] && !slk[i] && !check(i)) return;
            }
        }
    }
    void init(){
        for(int i=1; i<=N; i++){
            link_x[i] = link_y[i] = 0;
            visy[i] = false;
        }
        for(int i=1; i<=N; i++){
            hx[i] = 0;
            for(int j=1; j<=N; j++){
                if(hx[i] < mp[i][j]) hx[i] = mp[i][j];//hx初始化为x-y这条边的边权
            }
        }
    }
}km;
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            km.mp[i][j] = -inf_ll;//边权有负数,初始化边权为极小值
        }
    }
    for (int i=1;i<=m;i++){
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        km.mp[u][v]=w;
    }
    km.N = n;
    km.init();
    ll ans = 0;
    for (int i=1;i<=km.N;i++) km.bfs(i);
    for(int i=1; i<=n; i++){
        ans += km.mp[i][km.link_x[i]];
    }
    printf("%lld
",ans);
    for (int i=1;i<=n;i++) printf("%d%c",km.link_y[i],i == n ? '
' : ' ');
    return 0;
}