[BZOJ 1565][NOI2009]植物大战僵尸 最小割

传送门·Teleport!

题目大意

直接盗链…

解题报告

老样子，附赠样例:

Input:
3 3
5 1 0 1
10 1 0 0
15 2 0 0 0 1
-10 0
90 0
-20 2 1 0 1 1
80 1 2 1
10 1 2 1
40 0
Output:
125

有消耗有收入，有相互间的牵制关系，这实际上是一道最小割的题目。
设源点为S, 汇点为T，源点集为s，汇点集为t。
每个植物看成一个点，如果点u在s中，那么看做点u被消灭了。
对每个植物u，如果权值为正，那么连接一条S->T的权值为植物权值的边。
否然连接一条u->T的权值为植物权值的绝对值的边。
搞搞就发现所有正权植物权值和减去这么跑最小割的答案就是答案。
那么怎么进行选择的约束呢？
假设如果有一条u->v的权值为INF的边，那么u和v必然要么在最小割后被分配在同一个集合里，要么v在t中而u在s中。
考虑如果植物u保护了植物v，就可以用上面的方法进行约束，连接一条v->u的INF边，那么u可以被吃掉(在s中)或不被吃掉(不在s中)，而只有u在s中时v才能在s中(也被吃掉)
然后会有植物相互保护形成了一个“无敌环”的情况，这个环明显不能被最小割切开，我们为了不让这个环出现在s中，可以在环上随便找个点x连接一条x->T的INF边。原理很简单我就不多说了。

接下来上代码

代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>

const int INF = 0x3f3f3f3f;
const int MAXN = 35;

using std :: min;
using std :: max;

namespace isap {
    const int MAXD = MAXN*MAXN+100;
    const int MAXE = 500000;

    struct Node {
        int v, w, bk, nxt;
    } d[MAXE];
    int head[MAXD], etot;
    inline int addEdge (int a, int b, int c) {
        etot ++;
        d[etot].v = b;
        d[etot].w = c;
        d[etot].bk = etot + 1;
        d[etot].nxt = head[a];
        head[a] = etot;
        etot ++;
        d[etot].v = a;
        d[etot].w = 0;
        d[etot].bk = etot - 1;
        d[etot].nxt = head[b];
        head[b] = etot;
        return etot;
    }

    int dis[MAXD], vd[MAXD];
    int seq[MAXD*2];
    void bfs (int s) {
        int lef, rig;
        memset(dis, 0x3f, sizeof dis);
        dis[seq[lef = rig = 0] = s] = 0;
        while(lef <= rig) {
            int u = seq[lef++];
            for(int e = head[u]; e; e = d[e].nxt)
                if(dis[d[e].v] > dis[u] + 1) {
                    dis[d[e].v] = dis[u] + 1;
                    seq[++rig] = d[e].v;
                }
        }
    }
    int S, T, N;
    int dfs (int u, int val) {
        if(u == T) return val;
        int rest = val;
        for(int e = head[u]; e; e = d[e].nxt)
            if(d[e].w && dis[d[e].v]+1 == dis[u]) {
                int t = dfs(d[e].v, min(rest, d[e].w));
                rest -= t;
                d[e].w -= t;
                d[d[e].bk].w += t;
                if(!rest) return val;
                if(dis[S] >= N) return val - rest;
            }
        if(val == rest) {
            if(!(--vd[dis[u]])) {dis[S] = N; return 0;}
            dis[u] = N;
            for(int e = head[u]; e; e = d[e].nxt)
                if(d[e].w) dis[u] = min(dis[u], dis[d[e].v] + 1);
            ++ vd[dis[u]];
            return 0;
        }
        return val - rest;
    }

    int sap (int s, int t, int n) {
        S = s, T = t, N = n;
        bfs(T);
        for(int i = 1; i<=N; i++)
            if(dis[i] <= N) vd[dis[i]] ++;
        int flow = 0;
        while(dis[S] < N) flow += dfs(S, INF);
        return flow;
    }
}

struct Digraph {
    struct Node {
        int v, nxt;
    } d[500000];
    int head[MAXN*MAXN], etot;
    Digraph () {etot = 0;}
    inline int addEdge (int a, int b) {
        etot ++;
        d[etot].v = b;
        d[etot].nxt = head[a];
        head[a] = etot;
        return etot;
    }
    Node & operator [] (int index) {
        return d[index];
    }
};
Digraph inp;

inline int getInt () {
    int ret; char ch; bool f = false;
    while((ch = getchar()) < '0' || ch > '9') f ^= (ch == '-');
    ret = ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9') ret *= 10, ret += ch - '0';
    ungetc(ch, stdin);
    return f ? -ret : ret;
}

int N, M, vtot, colr;
int val[MAXN*MAXN];
int tag[MAXN*MAXN];
int cir[MAXN*MAXN], ctot;

void dfs(int u) {
    if(tag[u]) {
        if(tag[u] == colr) cir[++ctot] = u;
        return ;
    }
    tag[u] = colr;
    for(int e = inp.head[u]; e; e = inp[e].nxt)
        dfs(inp[e].v);
    tag[u] = -1;
}

inline int getVid(int row, int col) {
    return (row-1)*M+col;
}

int main () {
    int sum = 0, x, y;
    N = getInt(), M = getInt();
    for(int i = 1; i <= N; i++)
        for(int j = 1; j<=M; j++) {
            val[getVid(i, j)] = getInt();
            int rad = getInt(), id = getVid(i, j);
            if(val[id] > 0) sum += val[id];
            while(rad --) {
                x = getInt()+1, y = getInt()+1;
                inp.addEdge(getVid(x, y), id);
            }
            if(j!=M) inp.addEdge(id, getVid(i, j+1));
        }
    vtot = getVid(N, M);
    for(int i = 1; i<=vtot; i++)
        if(!tag[i]) colr++, dfs(i);
    int S = 1, T = S + vtot + 1;
    for(int i = 1; i<=ctot; i++)
        isap :: addEdge(S + cir[i], T, INF);
    for(int u = 1; u<=vtot; u++) {
        for(int e = inp.head[u]; e; e = inp[e].nxt)
            if(inp[e].v != u) isap :: addEdge(S + u, S + inp[e].v, INF);
        if(val[u] > 0) isap :: addEdge(S, S + u, val[u]);
        else isap :: addEdge(S + u, T, -val[u]);
    }
    sum -= isap :: sap(S, T, T);
    printf("%d\n", sum);
}