「BZOJ1565」[NOI2009]植物大战僵尸

Description

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

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

游戏的地图可以抽象为一个NNMM列的矩阵,行从上到下用00N1N–1编号,列从左到右用00M1M–1编号;在地图的每个位置上都放有一个Plant,为简单起见,我们把位于第rr行第cc列的植物记为PrP_r, cc

Plants分很多种,有攻击类、防守类和经济类等等。为了简单的描述每个Plant,定义Score和Attack如下:

Score[Pr,c]Score[P_r, c]

Zombie击溃植物PrP_r, c可获得的能源。若Score[Pr,c]Score[P_r, c]为非负整数,则表示击溃植物PrP_r, c可获得能源Score[Pr,c]Score[P_r, c],若为负数表示击溃Pr, c需要付出能源 Score[Pr,c]-Score[P_r, c]

Attack[Pr,c]Attack[P_r, c]

植物Pr_, c能够对Zombie进行攻击的位置集合。

Zombies必须从地图的右侧进入,且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说,对于第rr行的进攻,Zombies必须首先攻击PrP_r, M1M-1;若需要对PrP_r, c(0c<M1)c(0\leq c<M-1)攻击,必须将PrP_r,M1M-1, PrP_r, M2PrM-2\cdots P_r, c+1c+1先击溃,并移动到位置(r,c)(r, c)才可进行攻击。

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

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

Input

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

接下来N×M行描述每个位置上植物的信息。第r×M+c+1r\times M + c + 1行按照如下格式给出植物Pr,cP_r, c的信息:第一个整数为Score[Pr,c]Score[P_r, c], 第二个整数为集合Attack[Pr,c]Attack[P_r, c]中的位置个数ww,接下来ww个位置信息(r,c)(r', c'),表示PrP_r, c可以攻击位置第rr' 行第cc' 列。

Output

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

Sample Input

1
2
3
4
5
6
7
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0

Sample Output

1
25

HINT

20%20\%的数据满足1N,M51 \leq N, M \leq 5
40%40\%的数据满足1N,M101 \leq N, M \leq 10
100%100\%的数据满足1N20,1M30,10000Score100001 \leq N \leq 20,1 \leq M \leq 30,-10000 \leq Score \leq 10000

Solution

最大权闭合子图套路题。
对于正点,用ss连向它,容量为viv_i
对于负点,让它连向tt,容量为vi-v_i
右边的点,向左边的点连容量为infinf的边。(建图要反过来,左边连向右边)。
如果形成环的,直接别鸟他们。
最后跑最大流。
答案就是vimaxflow(vi0)\sum v_i - maxflow (v_i \ge 0)

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 20 * 31, M = 20*31*4 + N * N*3;

int n, m;
inline int id(int x, int y) {
return (x - 1) * m + y;
}
int a[N];
vector<int>p[N];
int ind[N];
bool vis[N];
void topsort() {
queue<int>q;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(!ind[id(i, j)]) q.push(id(i, j));
while(!q.empty()) {
int x = q.front(); q.pop();
vis[x] = 1;
for(int i = 0; i < p[x].size(); ++i){
int y = p[x][i];
if(!--ind[y]) q.push(y);
}
}
}
const int inf = 1e9;
struct Edge {
int u, v, nxt, f;
}e[M*2];
int head[N], en = 1;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en ,e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int s, t;
int d[N];
bool bfs() {
queue<int>q;
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f ){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1 && e[i].f) {
int y = e[i].v;
k = dinic(y, min(rest, e[i].f));
if(!k) continue;
e[i ^ 1].f += k;
e[i].f -= k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow - rest;
}
int main() {
n = read(), m = read();
s = n * m + 1;
t = n * m + 2;
int sum = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
a[id(i, j)] = read();
int w = read(), x = id(i, j);
for(int j = 1; j <= w; ++j) {
int nx = read() + 1, ny = read() + 1;
p[x].pb(id(nx, ny));
++ind[id(nx, ny)];
}
if(j > 1) p[x].pb(id(i, j - 1)), ++ind[id(i, j - 1)];
}
topsort();
int tot= n * m;
for(int i = 1; i <= tot; ++i)
if(vis[i]) {
if(a[i] > 0) addedge(s, i, a[i]), sum += a[i];
else addedge(i, t, -a[i]);
for(int j = 0; j < p[i].size(); ++j)
if(vis[p[i][j]])
addedge(p[i][j], i, inf);
}
int res = 0, y;
while(bfs()) {
while(y = dinic(s, inf)) res += y;
}
writeln(sum - res);
return 0;
}