@[Pandingding](/user/722468)
```
#include <bits/stdc++.h>
using namespace std;
long long n,m,a[505][505],mc[505],s[505],p[505],x[505],e[505];
int vx[505],vy[505];
void fun(long long u)
{
long long xx,y = 0,yy = 0,d;
memset(p,0,sizeof(p));
for(long long i = 1;i <= n;i++)
{
s[i] = 1e18;
}
mc[y] = u;
while(true)
{
xx = mc[y];
d = 1e18;
vy[y] = 1;
for(long long i = 1;i <= n;i++)
{
if(vy[i] != 0)
{
continue;
}
if(s[i] > x[xx] + e[i] - a[xx][i])
{
s[i] = x[xx] + e[i] - a[xx][i];
p[i] = y;
}
if(s[i] < d)
{
d = s[i];
yy = i;
}
}
for(long long i = 0;i <= n;i++)
{
if(vy[i] != 0)
{
x[mc[i]] -= d;
e[i] += d;
}
else
{
s[i] -= d;
}
}
y = yy;
if(mc[y] == -1)
{
break;
}
}
while(y != 0)
{
mc[y] = mc[p[y]];
y = p[y];
}
}
long long km()
{
memset(mc,-1,sizeof(mc));
memset(x,0,sizeof(x));
memset(e,0,sizeof(e));
for(long long i = 1;i <= n;i++)
{
memset(vy,0,sizeof(vy));
fun(i);
}
long long ans = 0;
for(long long i = 1;i <= n;i++)
{
if(mc[i] != -1)
{
ans += a[mc[i]][i];
}
}
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
a[i][j] = -1e18;
}
}
for(long long i = 1;i <= m;i++)
{
long long u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
a[u][v] = w;
}
printf("%lld\n",km());
for(long long i = 1;i <= n;i++)
{
printf("%lld ",mc[i]);
}
return 0;
}
```
by OIDragon @ 2023-11-26 09:17:50