时间复杂度（$O^3$）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 505;
const ll inf = 0x3f3f3f3f3f;
ll n, m, a[N][N], match[N];
ll slack[N], pre[N], ex[N], ey[N];
bool v1[N], v2[N];
void find(ll u){
    ll x, y = 0, yy, del;
    memset(pre, 0, sizeof(pre));
    for(ll i = 1;i <= n;i ++) slack[i] = inf;
    match[y] = u;
    while(1){
        x = match[y], del = inf, v2[y] = 1;
        for(ll i = 1;i <= n;i ++){
            if(v2[i]) continue;
            if(slack[i] > ex[x] + ey[i] - a[x][i]){
                slack[i] = ex[x] + ey[i] - a[x][i];
                pre[i] = y;
            }
            if(slack[i] < del) del = slack[i], yy = i;
        }
        for(ll i = 0;i <= n;i ++){
            if(v2[i]) ex[match[i]] -= del, ey[i] += del;
            else slack[i] -= del;
        }
        y = yy;
        if(match[y] == -1) break;
    }
    while(y){match[y] = match[pre[y]]; y = pre[y];}
}
ll KM(){
    memset(match, -1, sizeof(match));
    memset(ex, 0, sizeof(ex));
    memset(ey, 0, sizeof(ey));
    for(ll i = 1;i <= n;i ++){
        memset(v2, 0, sizeof(v2));
        find(i);
    }
    ll res = 0;
    for(ll i = 1;i <= n;i ++)
        if(match[i] != -1) res += a[match[i]][i];
    return res;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            a[i][j] = -inf;
    for(ll i = 1;i <= m;i ++){
        ll u, v, w;
        scanf("%lld%lld%lld",&u,&v,&w);
        a[u][v] = w;
    }
    printf("%lld\n", KM());
    for(ll i = 1;i <= n;i ++)
        printf("%lld ",match[i]);
    return 0;
}