# 某岛

… : "…アッカリ～ン . .. . " .. .
September 7, 2012

## BZOJ 1497. [NOI2006]最大获利

### 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, _m){
int x, y, z; RD(x, y, z); Sum += z;
}
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

init(); OT(Sum - Dinitz());
}