BZOJ 1565: [NOI2009]植物大战僵尸

Description

Plants vs. Zombies（PVZ）是最近十分风靡的一款小游戏。Plants（植物）和Zombies（僵尸）是游戏的主角，其中Plants防守，而Zombies进攻。该款游戏包含多种不同的挑战系列，比如Protect Your Brain、Bowling等等。其中最为经典的，莫过于玩家通过控制Plants来防守Zombies的进攻，或者相反地由玩家通过控制Zombies对Plants发起进攻。

现在，我们将要考虑的问题是游戏中Zombies对Plants的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，Plants和Zombies，每个Plant有一个攻击位置集合，它可以对这些位置进行保护；而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。

游戏的地图可以抽象为一个N行M列的矩阵，行从上到下用0到N–1编号，列从左到右用0到M–1编号；在地图的每个位置上都放有一个Plant，为简单起见，我们把位于第r行第c列的植物记为Pr,c。

Plants分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个Plant，定义Score和Attack如下： Score[Pr,c]Zombie击溃植物Pr,c可获得的能源。若Score[Pr,c]为非负整数，则表示击溃植物Pr,c可获得能源Score[Pr,c]，若为负数表示击溃Pr,c需要付出能源-Score[Pr,c]。Attack[Pr,c]植物Pr,c能够对Zombie进行攻击的位置集合。 Zombies必须从地图的右侧进入，且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说，对于第r行的进攻，Zombies必须首先攻击Pr,M-1；若需要对Pr,c（0≤c<M-1）攻击，必须将Pr,M-1,Pr,M-2…Pr,c+1先击溃，并移动到位置(r,c)才可进行攻击。

在本题的设定中，Plants的攻击力是无穷大的，一旦Zombie进入某个Plant的攻击位置，该Zombie会被瞬间消灭，而该Zombie没有时间进行任何攻击操作。因此，即便Zombie进入了一个Plant所在的位置，但该位置属于其他植物的攻击位置集合，则Zombie会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，Plant的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。

Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套Zombies的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

Input

第一行包含两个整数N,M，分别表示地图的行数和列数。

接下来N×M行描述每个位置上植物的信息。第r×M+c+ 1行按照如下格式给出植物Pr,c的信息：第一个整数为Score[Pr,c],第二个整数为集合Attack[Pr,c]中的位置个数w，接下来w个位置信息（r’,c’），表示Pr,c可以攻击位置第r’行第c’列。

Output

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

Sample Input

Sample Output

1
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行中的任何植物。

100%的数据满足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 。

Solution

（当时PVZ真的是太火辣！现在PVZ貌似做出来一个3D的FPS…）

一个植物被吃掉的先决条件是他右边所有植物和保护他的所有植物都被吃掉。如果把他右边的植物都看成保护了这颗植物，那么要吃掉植物x，先要把所有保护他的植物吃掉。考虑最大权闭合子图。如果i保护j也就是说吃j前先吃i，连接一条j->i，容量为INF的边。但是这样跑貌似有环。于是我们反向建边，建到图中，然后拓扑序找出所有的环，在环上DFS找出环保护的点，把这些点删掉。按照原图中（不反向的边）流量为INF，S到正权点流量为得分，负权点流量到T流量为负的分，重建网络流图，跑一遍最大流，我们得到了最小割。那么答案就是所有正权点减去最小割。

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
int id[105][105], n, m, sc[105][105], S, T, tot;
struct Flow_type {
    int cnte, h[50005], sum;
    int tail, head, d[50005], cur[50005], Q[50005];
    struct edge_type {
        int to, next, r;
    } edge[500005];
    void ins(int x, int y, int r) {
        edge[++cnte].to = y;
        edge[cnte].next = h[x];
        edge[cnte].r = r;
        h[x] = cnte;
        edge[++cnte].to = x;
        edge[cnte].next = h[y];
        edge[cnte].r = 0;
        h[y] = cnte;
    }
    bool bfs() {
        tail = head = 0;
        for (int i = S; i <= T; ++i) d[i] = -1;
        Q[tail++] = S;
        d[S] = 0;
        int now;
        while (head < tail) {
            now = Q[head++];
            for (int i = h[now]; i; i = edge[i].next) {
                if (d[edge[i].to] == -1 && edge[i].r) {
                    d[edge[i].to] = d[now] + 1;
                    Q[tail++] = edge[i].to;
                }
            }
        }
        return d[T] != -1;
    }
    int dfs(int now, int a) {
        if (T == now || a == 0) return a;
        int ret = 0, f;
        for (int &i = cur[now]; i; i = edge[i].next) {
            if (d[edge[i].to] != d[now]+1) continue;
            if (f = dfs(edge[i].to, min(a, edge[i].r))) {
                a -= f;
                ret += f;
                edge[i].r -= f;
                edge[i^1].r += f;
                if (a == 0) break;
            }
        }
        if (ret == 0) d[now] = -1;
        return ret;
    }
    int Dinic() {
        int ret = 0;
        while (bfs()) {
            for (int i = S; i <= T; ++i)
                cur[i] = h[i];
            ret += dfs(S, INF);
        }
        return ret;
    }
} F;
struct SCC_type {
    int cnte, h[50005], sta[50005], tail, rd[50005];
    bool insta[50005], vis[50005];
    struct edge_type {
        int to, next;
    } edge[500005];
    void ins(int x, int y) {
        edge[++cnte].to = y;
        edge[cnte].next = h[x];
        ++rd[y];
        h[x] = cnte;
    }
    void dfs(int now) {
        for (int i = h[now]; i; i = edge[i].next) {
            if (vis[edge[i].to]) {
                vis[edge[i].to] = false;
                dfs(edge[i].to);
            }
        }
    }
    void Huan () {
        for (int i = 2; i <= tot; ++i) {
            if (rd[i] == 0)
                sta[++tail] = i;
        }
        int now;
        while (tail) {
            now = sta[tail--];
            vis[now] = true;
            for (int i = h[now]; i; i = edge[i].next) {
                if (vis[edge[i].to]) continue;
                --rd[edge[i].to];
                if (!rd[edge[i].to]) sta[++tail] = edge[i].to;
            }
        }
        tail = 0;
        for (int i = 2; i <= tot; ++i)
            if (!vis[i]) dfs(i);
    }
    void Build_Flow () {
        for (int x = 1; x <= n; ++x)
            for (int y = 1; y <= m; ++y) {
                int i = id[x][y];
                if (!vis[i]) continue;
                if (sc[x][y] > 0) {
                    F.sum += sc[x][y];
                    F.ins(S, i, sc[x][y]);
                }
                if (sc[x][y] < 0) {
                    F.ins(i, T, -sc[x][y]);
                }
                for (int j = h[i]; j; j = edge[j].next) {
                    if (!vis[edge[j].to]) continue;
                    F.ins(edge[j].to, i, INF);
                }
            }
    }
} G;
int main() {
    n = getint(); m = getint(); S = 1; tot = 1; F.cnte = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            id[i][j] = ++tot;
    T = tot + 1;
    int x, y;
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k < m; ++k)
            for (int j = k + 1; j <= m; ++j) G.ins(id[i][j], id[i][k]);
        for (int j = 1; j <= m; ++j) {
            sc[i][j] = getint();
            int w = getint();
            while (w--) {
                x = getint(); y = getint();
                G.ins(id[i][j], id[x + 1][y + 1]);
            }
        }
    }
    G.Huan();
    G.Build_Flow();
    int ans = F.Dinic();
    printf("%d", F.sum - ans);
    return 0;
}