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

External link:

http://www.lydsy.com/JudgeOnline/problem.php?id=1497

Posted by xiaodao
Category: BZOJ
Tags: 最大权闭合子图