最小点覆盖、最大独立集、最小路径点覆盖、最小路径重复点覆盖
最大匹配数 = 最小点覆盖 = 总点数-最大独立集 = 总点数-最小路径覆盖
二分图最大权完美匹配
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<string,int> PSI;
#define f first
#define s second
#define pb push_back
#define SPO(n) fixed << setprecision(n)
const int N = 510 , INF = 1e18;
int pre[N],love[N][N];
int valx[N],valy[N];
bool stx[N],sty[N];
int match[N],slack[N];
int n,m;
void find(int u)
{
int x,y=0,yy=0,delta;
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++) slack[i]=INF;
match[y]=u;
while(1)
{
x=match[y];delta=INF;sty[y]=1;
for(int i=1;i<=n;i++)
{
if(sty[i])continue;
if(slack[i]>valx[x]+valy[i]-love[x][i])
{
slack[i]=valx[x]+valy[i]-love[x][i];
pre[i]=y;
}
if(slack[i]<delta){delta=slack[i];yy=i;}
}
for(int i=0;i<=n;i++)
{
if(sty[i])valx[match[i]]-=delta,valy[i]+=delta;
else slack[i]-=delta;
}
y=yy;
if(match[y]==-1)break;
}
while(y){match[y]=match[pre[y]];y=pre[y];}
}
int km()
{
memset(match,-1,sizeof match);
memset(valx,0,sizeof valx);
memset(valy,0,sizeof valy);
for(int i=1;i<=n;i++)
{
memset(sty,0,sizeof sty);
find(i);
}
int res=0;
for(int i=1;i<=n;i++)
if(match[i]!=-1)res+=love[match[i]][i];
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
love[i][j]=-INF;
while (m -- )
{
int a,b,c;
cin>>a>>b>>c;
love[a][b]=c;
}
cout<<km()<<endl;
for(int i=1;i<=n;i++)
cout<<match[i]<<' ';
return 0;
}