我比较菜，如果问题比较傻请轻点骂。。。

就是这个题我写了一个 KM :

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

namespace Legendgod {
	namespace Read {
//		#define Fread
		#ifdef Fread
		const int Siz = (1 << 21) + 5;
		char *iS, *iT, buf[Siz];
		#define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
		#define getchar gc
		#endif
		template <typename T>
		void r1(T &x) {
		    x = 0;
			char c(getchar());
			int f(1);
			for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
			for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
			x *= f;
		}
		template <typename T, typename...Args>
		void r1(T &x, Args&...arg) {
			r1(x), r1(arg...);
		}
		#undef getchar
	}

using namespace Read;
const int maxn = 5e2 + 5;
typedef long long int64;
const int64 inf = 1e15;///!!!!
int a[maxn], n, m;
int mt[maxn], pre[maxn];
int64 ex[maxn], ey[maxn], sl[maxn], vc[maxn][maxn];
bool vis[maxn];

void bfs(int u) {
    int i, j, y(0), yy(0);
    memset(pre, 0, sizeof(pre));
    for(int i = 1; i <= n; ++ i) sl[i] = inf;
    mt[y] = u;
    while(1) {
        int cur = mt[y]; int64 tmp(inf); vis[y] = 1;
        for(int i = 1; i <= n; ++ i) if(!vis[i]) {
            if(sl[i] > ex[cur] + ey[i] - vc[cur][i]) {
                sl[i] = ex[cur] + ey[i] - vc[cur][i];
                pre[i] = y;
            }
            if(sl[i] < tmp) tmp = sl[i], yy = i;
        }
        for(int i = 0; i <= n; ++ i)
            if(vis[i]) ey[i] += tmp, ex[mt[i]] -= tmp;
            else sl[i] -= tmp;
        y = yy;
        if(mt[y] == -1) break;
    }
    while(y) mt[y] = mt[pre[y]], y = pre[y];
}

int64 KM() {
    memset(ex, 0, sizeof(ex));
    memset(ey, 0, sizeof(ey));
    memset(mt, -1, sizeof(mt));
    for(int i = 1; i <= n; ++ i) {
        memset(vis, 0, sizeof(vis));
        bfs(i);
    }
    int64 res(0);
    for(int i = 1; i <= n; ++ i) if(mt[i] != -1)
        res += vc[mt[i]][i];
    return res;
}

signed main() {
	int i, j;
    r1(n, m);
    for(i = 1; i <= n; ++ i) r1(a[i]);
    memset(vc, 0x3f, sizeof(vc));
//    printf("$ %d\n", vc[1][1]);
    for(i = 1; i <= m; ++ i) {
        int u, v, w; r1(u, v, w);
        vc[u][v] = w;
    }
    for(int k = 1; k <= n; ++ k) for(i = 1; i <= n; ++ i) for(j = 1; j <= n; ++ j)
        vc[i][j] = min(vc[i][j], vc[i][k] + vc[k][j]);
    for(i = 1; i <= n; ++ i) vc[i][i] = a[i];
    for(i = 1; i <= n; ++ i) for(j = 1; j <= n; ++ j) vc[i][j] *= -1;
    printf("%lld\n", - KM());
	return 0;
}

}


signed main() { return Legendgod::main(), 0; }//

不是很清楚这个 inf 应该设多大，求助大佬。