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

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

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18;
const int M=505;

int n,m;
int g[M][M];
bool vis[M];
int slack[M];
int match[M],pre[M];
int dx[M],dy[M];

void bfs(int x) {
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    fill(slack,slack+n+1,inf);
    int y=0,num,id;
    match[y]=x;
    while(match[y]) {
        x=match[y];
        vis[y]=1;
        num=inf;
        for(int i=1;i<=n;i++) {
            if(vis[i])continue;
            if(slack[i]>dx[x]+dy[i]-g[x][i])
                slack[i]=dx[x]+dy[i]-g[x][i],pre[i]=y;
            if(slack[i]<num)num=slack[i],id=i;
        }
        for(int i=0;i<=n;i++) {
            if(vis[i])dx[match[i]]-=num,dy[i]+=num;
            else slack[i]-=num;
        }
        y=id;
    }
    while(y)match[y]=match[pre[y]],y=pre[y];
}

int km() {
    for(int i=1;i<=n;i++)bfs(i);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(match[i])ans+=g[match[i]][i];
    return ans;
}

signed main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        g[i][j]=-inf;
    while(m--) {
        int x,y,w;
        cin>>x>>y>>w;
        g[x][y]=max(g[x][y],w);
    }
    cout<<km()<<endl;
    for(int i=1;i<=n;i++)cout<<match[i]<<' ';
    return 0;
}