首页 > 题解 > bzoj 1565 [NOI2009]植物大战僵尸

bzoj 1565 [NOI2009]植物大战僵尸

Description

Input

Output

仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。

Sample Input

3 2

10 0

20 0

-10 0

-5 1 0 0

100 1 2 1

100 0

Sample Output

25

HINT

在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为,首先进攻P1,1, P0,1,此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护,所以无法攻击第2行中的任何植物。
【大致数据规模】
约20%的数据满足1 ≤ N, M ≤ 5;
约40%的数据满足1 ≤ N, M ≤ 10;
约100%的数据满足1 ≤ N ≤ 20,1 ≤ M ≤ 30,-10000 ≤ Score ≤ 10000 。

题解

手玩下样例发现有环的情况,进而发现强连通分量和被强连通分量保护的点都不能吃

那么直接拓扑排序一下,不能被排序的就是可以吃的。

然后就是裸的最大权联通子图了

#include <cstdio>
#include <cstring>
#include <queue>
#define M 1000010
#define N 1010
using namespace std;
const int inf = 0x3f3f3f3f;
struct flows {
    struct node {
        int to, next, flow;
    } e[M];
    int tot, st[N], dis[N], cur[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e),
        memset(st, -1, sizeof st);
    }
    void add(int x, int y, int z) {
        e[++tot].to = y;
        e[tot].flow = z;
        e[tot].next = st[x];
        st[x] = tot;
    }
    void add_edge(int x, int y, int z) {
//      printf("%d %d %d\n", x, y, z);
        add(x, y, z), add(y, x, 0);
    }
    queue <int> que;
    int bfs(int S, int T) {
        memcpy(cur, st, sizeof st);
        memset(dis, 0, sizeof dis);
        while (!que.empty()) que.pop();
        que.push(S);
        dis[S] = 1;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow && !dis[e[i].to]) {
                    dis[e[i].to] = dis[now] + 1;
                    if (e[i].to == T) return 1;
                    que.push(e[i].to);
                }
        }
        return 0;
    }
    int finds(int now, int T, int flow) {
        if (now == T)
            return flow;
        int f;
        for (int i = cur[now]; ~i; i = e[i].next) {
            cur[now] = i;
            if (e[i].flow && dis[e[i].to] == dis[now] + 1 &&
                (f = finds(e[i].to, T, min(flow, e[i].flow)))) {
                e[i].flow -= f;
                e[i^1].flow += f;
                return f;
            }
        }
        return 0;
    }
    int dinic(int S, int T) {
        int flow = 0, x;
        while(bfs(S, T)) {
            while(x = finds(S, T, inf)) {
                flow += x;
            }
        }
        return flow;
    }
}flow;
int n, m, all, x, y;
int ge(int x, int y) { return (x - 1) * m + y; }
struct edge {
    int to, next;
}e[M];
int st[N], tot, d[N], can[N], v[N];
void add(int x, int y) {
    e[++tot].to = y;
    e[tot].next = st[x];
    st[x] = tot;
}
queue <int> que;
void topsort() {
    for (int i = 1; i <= n * m; ++i)
        if (d[i] == 0)
            que.push(i), can[i] = 1;
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        for (int i = st[now]; i; i = e[i].next) {
                d[e[i].to]--;
                if (!d[e[i].to])
                    que.push(e[i].to), can[e[i].to] = 1;
            }
    }
}
main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int p;
            scanf("%d%d", &v[ge(i, j)], &p);
            for (int k = 1; k <= p; ++k)
                scanf("%d%d", &x, &y), x++, y++,
                add(ge(i, j), ge(x, y)), d[ge(x, y)]++;
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 2; j <= m; ++j)
            add(ge(i, j), ge(i, j - 1)), d[ge(i, j - 1)]++;
    topsort();
//  for (int i = 1; i <= n * m; ++i)
//      if (can[i]) printf("%d ", i);
    int S = 0, T = n * m + 1, ans = 0;
    flow.init();
    for (int i = 1; i <= n * m; ++i)
        if (can[i]) {
            if (v[i] > 0)
                flow.add_edge(S, i, v[i]), ans += v[i];
            else
                flow.add_edge(i, T, -v[i]);
            for (int j = st[i]; j; j = e[j].next)
                if (can[e[j].to])
                    flow.add_edge(e[j].to, i, inf);
        }
    printf("%d\n", ans - flow.dinic(S, T));
}