…<\/p>\n
<\/p>\n
Tags: \u6700\u5927\u6743\u95ed\u5408\u5b50\u56fe
\n… \u6bcf\u4e2a\u7b80\u5355\u5272\u5bf9\u5e94\u4e00\u4e2a\u95ed\u5408\u5b50\u56fe\u3002(\u6ca1\u6709\u9009\u4e2d\u7684\u6b63\u6743\u70b9 + \u9009\u4e2d\u7684\u8d1f\u6743\u70b9\u3002\u3002\u3002
\n Dinitz .. ( 700+ \/ 200+<\/a>
\n\u3002(\u3002\u3002\u636e\u8bf4\u6362\u4e00\u79cd\u7b49\u4ef7\u5efa\u56fe\u53ef\u4ee5\u83b7\u5f97\u8c1c\u306e\u4f18\u5316\u3002\u3002\u3002<\/p>\n\r\n\r\nconst int _N = 5009, _M = 50009;\r\nconst int N = _N + _M + 9, M = 2 * (N + _M * 3) + 9;\r\n\r\nint D[N], hd[N], suc[M], to[M], cap[M];\r\nint n, m, s, t;\r\n\r\ninline void add_edge(int x, int y, int c){\r\n suc[m] = hd[x], to[m] = y, cap[m] = c, hd[x] = m++;\r\n suc[m] = hd[y], to[m] = x, cap[m] = 0, hd[y] = m++;\r\n}\r\n\r\ninline void add_edgee(int x, int y, int c){\r\n suc[m] = hd[x], to[m] = y, cap[m] = c, hd[x] = m++;\r\n suc[m] = hd[y], to[m] = x, cap[m] = c, hd[y] = m++;\r\n}\r\n\r\n#define v to[i]\r\n#define c cap[i]\r\n#define r cap[i^1]\r\n\r\nbool bfs(){\r\n static int Q[N]; int cz = 0, op = 1;\r\n fill(D, D+n, 0), D[Q[0] = s] = 1; while (cz < op){\r\n int u = Q[cz++]; REP_G(i, u) if (!D[v] && c){\r\n D[Q[op++] = v] = D[u] + 1;\r\n if (v == t) return 1;\r\n }\r\n }\r\n return 0;\r\n}\r\n\r\nint Dinitz(){\r\n\r\n assert(to[0] == s);\r\n\r\n int max_flow = 0; while (bfs()){\r\n\r\n static int sta[N], cur[N]; int top = 0;\r\n sta[0] = 0, cur[s] = hd[s]; while (top != -1){\r\n\r\n int u = to[sta[top]], i; if (u == t){\r\n int d = INF; REP_1(ii, top) i = sta[ii], checkMin(d, c); max_flow += d;\r\n DWN_1(ii, top, 1){i = sta[ii], c -= d, r += d; if (!c) top = ii - 1;}\r\n u =to[sta[top]];\r\n }\r\n\r\n for (i=cur[u];i;i=suc[i])\r\n if (D[u] + 1 == D[v] && c) break;\r\n\r\n if (!i) D[u] = 0, --top;\r\n else {\r\n cur[u] = suc[i], cur[v] = hd[v];\r\n sta[++top] = i;\r\n }\r\n }\r\n }\r\n return max_flow;\r\n}\r\n\r\n#undef r\r\n#undef c\r\n\r\nint Sum;\r\n\r\nvoid init(){\r\n int _n, _m; RD(_n, _m), m = 2 , t = _n+_m+1, n = t+1;\r\n \/\/fill(hd, hd+n, 0); Sum = 0;\r\n REP_1(i, _n) add_edge(s, i, RD());\r\n REP_1(i, _m){\r\n int x, y, z; RD(x, y, z); Sum += z;\r\n add_edge(_n+i, t, z);\r\n add_edge(x, _n+i, INF);\r\n add_edge(y, _n+i, INF);\r\n }\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n\r\n init(); OT(Sum - Dinitz());\r\n}\r\n\r\n<\/pre>\nExternal link: <\/h3>\n