很明显这是一个最小割的题。然后想怎么最小割。
我们先把所有正贡献加起来，然后把可能失去的正贡献和可能获得的负贡献建图跑最小割即可。
#include <bits/stdc++.h>
#define llong long long
#define N 60004
#define M 200005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}constexpr int inf = 1e9+7;int n, m, s;
int to[M<<1], siz[M<<1], nxt[M<<1], head[N], gsiz = 1;
#define mkarc(u,v,w) (++gsiz, to[gsiz]=v, siz[gsiz]=w, nxt[gsiz]=head[u], head[u]=gsiz)
int lev[N], cur[N];int que[N], he, ta;
inline bool bfs(){for(int i = 1; i <= n+m+2; ++i) cur[i] = head[i], lev[i] = 0;que[he = ta = 1] = 1, lev[1] = 1;while(he <= ta){int u = que[he++];if(u == 2) return true;for(int i = head[u]; i; i = nxt[i]){int v = to[i];if(lev[v] || !siz[i]) continue;lev[v] = lev[u]+1;que[++ta] = v;}}return false;
}
inline int dfs(int u, int f){if(u == 2) return f;int res = 0;for(int &i = cur[u]; i; i = nxt[i]){int v = to[i];if(lev[v] != lev[u]+1 || !siz[i]) continue;int d = dfs(v, min(f, siz[i]));if(!d) lev[v] = -1;siz[i] -= d, f -= d;siz[i^1] += d, res += d;if(!f) break;}return res;
}
inline int dinic(){int res = 0;while(bfs()) res += dfs(1, inf);return res;
}int main(){freopen("in.txt", "r", stdin);read(n, m);for(int i = 1, x; i <= n; ++i){read(x);mkarc(1, i+2, x), mkarc(i+2, 1, 0);}for(int i = 1, v1, v2, x; i <= m; ++i){read(v1, v2, x), s += x;mkarc(v1+2, i+n+2, inf), mkarc(i+n+2, v1+2, 0);mkarc(v2+2, i+n+2, inf), mkarc(i+n+2, v2+2, 0);mkarc(i+n+2, 2, x), mkarc(2, i+n+2, 0);}printf("%d", s-dinic());return 0;
}