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());
}
