KMdfs9分求调

//P6577 【模板】二分图最大权完美匹配——KM算法
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 510;
const int INF = 2147483647;

int love[MAXN][MAXN]; //love_i,j存左i值至右j的权值
int ex_girl[MAXN]; //女生期望值
int ex_boy[MAXN]; //男生
bool vis_girl[MAXN]; //记录已匹配女生
bool vis_boy[MAXN]; //记录已匹配男生
int match[MAXN]; //记录对象
int slack[MAXN]; //最小减少值
int n,m;

bool dfs(int girl){
	vis_girl[girl] = true;
	for(int boy = 1; boy<=n; boy++){
		if(vis_boy[boy]) continue;
		int gap=ex_girl[girl]+ex_boy[boy]-love[girl][boy];
		if(!gap){
			vis_boy[boy] = true;
			if(!match[boy] || dfs(match[boy])){
				match[boy]=girl;
				return true;
			}
		}else{
			slack[boy]=min(slack[boy],gap);
		}
	}
	return false;
}

int KM(){
	memset(match,0,sizeof match);
	memset(ex_boy,0,sizeof ex_boy);
	
	for(int i = 1; i<=n; i++){
		ex_girl[i]=love[i][1];
		for(int j = 2; j<=n; j++){
			ex_girl[i]=max(ex_girl[i],love[i][j]);
		}
	}
	for(int i = 1; i<=n; i++){
		fill(slack+1,slack+1+n,INF);
		while(true){
			memset(vis_girl,0,sizeof vis_girl);
			memset(vis_boy,0,sizeof vis_boy);
			if(dfs(i)) break;
			int d=INF;
			for(int j = 1; j<=n; j++){
				if(!vis_boy[j]) d=min(d,slack[j]);
			}
			for(int j = 1; j<=n; j++){
				if(vis_girl[j]) ex_girl[j]-=d;
				if(vis_boy[j]) ex_boy[j]+=d;
				else slack[j]-=d;
			}
		}
	}
	int res = 0;
	for(int i = 1; i<=n; i++) res+=love[match[i]][i];
	return res;
}

signed main(){
	cin>>n>>m;
	while(m--){
		register int u,v,t;
		cin>>u>>v>>t;
		love[u][v]=t;
	}
	cout<<KM()<<'\n';
	for(int i = 1; i<=n; i++){
		cout<<match[i]<<" ";
	}
	return 0;
}