### Brief description:

…

### Analysis:

Tags: 最大权闭合子图

… 每个简单割对应一个闭合子图。(没有选中的正权点 + 选中的负权点。。。

Dinitz .. ( 700+ / 200+

。(。。据说换一种等价建图可以获得谜の优化。。。

const int _N = 5009, _M = 50009; const int N = _N + _M + 9, M = 2 * (N + _M * 3) + 9; int D[N], hd[N], suc[M], to[M], cap[M]; int n, m, s, t; inline void add_edge(int x, int y, int c){ suc[m] = hd[x], to[m] = y, cap[m] = c, hd[x] = m++; suc[m] = hd[y], to[m] = x, cap[m] = 0, hd[y] = m++; } inline void add_edgee(int x, int y, int c){ suc[m] = hd[x], to[m] = y, cap[m] = c, hd[x] = m++; suc[m] = hd[y], to[m] = x, cap[m] = c, hd[y] = m++; } #define v to[i] #define c cap[i] #define r cap[i^1] bool bfs(){ static int Q[N]; int cz = 0, op = 1; fill(D, D+n, 0), D[Q[0] = s] = 1; while (cz < op){ int u = Q[cz++]; REP_G(i, u) if (!D[v] && c){ D[Q[op++] = v] = D[u] + 1; if (v == t) return 1; } } return 0; } int Dinitz(){ assert(to[0] == s); int max_flow = 0; while (bfs()){ static int sta[N], cur[N]; int top = 0; sta[0] = 0, cur[s] = hd[s]; while (top != -1){ int u = to[sta[top]], i; if (u == t){ int d = INF; REP_1(ii, top) i = sta[ii], checkMin(d, c); max_flow += d; DWN_1(ii, top, 1){i = sta[ii], c -= d, r += d; if (!c) top = ii - 1;} u =to[sta[top]]; } for (i=cur[u];i;i=suc[i]) if (D[u] + 1 == D[v] && c) break; if (!i) D[u] = 0, --top; else { cur[u] = suc[i], cur[v] = hd[v]; sta[++top] = i; } } } return max_flow; } #undef r #undef c int Sum; void init(){ int _n, _m; RD(_n, _m), m = 2 , t = _n+_m+1, n = t+1; //fill(hd, hd+n, 0); Sum = 0; REP_1(i, _n) add_edge(s, i, RD()); REP_1(i, _m){ int x, y, z; RD(x, y, z); Sum += z; add_edge(_n+i, t, z); add_edge(x, _n+i, INF); add_edge(y, _n+i, INF); } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif init(); OT(Sum - Dinitz()); }