[BZOJ 1565][NOI 2009] 植物大战僵尸

题目大意

游戏棋盘为 \(n\times m\),行从上到下从 \(0\) 开始编号,列从左到右从 \(0\) 开始编号(僵尸从 \(m - 1\) 列进入)。每一个植物有一个攻击范围,会瞬间消灭进入范围内的僵尸(僵尸无法吃到该位置上的植物);同时,每一个植物有一个分数 \(score_i\) ,在僵尸吃了该植物后会获得相应分数。求僵尸可获得的最多分数。

\(1 \leqslant n \leqslant 20\)

\(1 \leqslant m \leqslant 30\)

\(-10,000 \leqslant score_i \leqslant 10,000\)

题目链接

BZOJ 1565

CodeVS 1846

题解

在网格上连单向边 \((u, \; v)\) 表示,在吃掉 \(v\) 之前,必须先吃掉 \(u\);程序实现时,从每个植物向其保护的位置连边,从每个格子向左边的格子连边。注意到,当图里出现了环时,环上的点、环延伸出去的点都不能被吃掉;对于剩下的点,即求最大权闭合图。从源点向正权点连容量为权值的边,从负权点向汇点连容量为权值绝对值的边,对于原图中的边,反向连入(如果不想反向,源点连负权,汇点连正权),跑最大流。在找环时,用拓扑排序,没有遍历到的点就是吃不掉的点。

代码

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
#include <cstdio>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
// #define DBG
const int MAXN = 20;
const int MAXM = 30;
struct Edge;
struct Node {
Edge *e, *curr;
int level;
} N[MAXN * MAXM + 2];
struct Edge {
Node *u, *v;
Edge *next, *rev;
int cap, flow;
Edge(Node *u, Node *v, int cap) : u(u), v(v), cap(cap), flow(0), next(u->e) {}
};
void addEdge(int u, int v, int cap) {
#ifdef DBG
printf("edge : %d --> %d, cap = %d\n", u, v, cap);
#endif
N[u].e = new Edge(&N[u], &N[v], cap);
N[v].e = new Edge(&N[v], &N[u], 0);
N[u].e->rev = N[v].e;
N[v].e->rev = N[u].e;
}
namespace Dinic {
bool makeLevelGraph(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) N[i].level = 0;
std::queue<Node *> q;
q.push(s);
s->level = 1;
while (!q.empty()) {
Node *u = q.front();
q.pop();
for (Edge *e = u->e; e; e = e->next) {
if (e->cap > e->flow && e->v->level == 0) {
e->v->level = u->level + 1;
if (e->v == t) return true;
q.push(e->v);
}
}
}
return false;
}
int findPath(Node *s, Node *t, int limit = INT_MAX) {
if (s == t) return limit;
for (Edge *&e = s->curr; e; e = e->next) {
if (e->cap > e->flow && e->v->level == s->level + 1) {
int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
if (flow > 0) {
e->flow += flow;
e->rev->flow -= flow;
return flow;
}
}
}
return 0;
}
int solve(int s, int t, int n) {
int res = 0;
while (makeLevelGraph(&N[s], &N[t], n)) {
for (int i = 0; i < n; i++) N[i].curr = N[i].e;
int flow;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}
return res;
}
}
struct EdgeT;
struct NodeT {
EdgeT *e;
int deg, id;
bool vis;
} NT[MAXN * MAXM + 1];
struct EdgeT {
NodeT *u, *v;
EdgeT *next;
EdgeT(NodeT *u, NodeT *v) : u(u), v(v), next(u->e) {}
};
void addEdgeT(int u, int v) {
#ifdef DBG
printf("edgeT : %d --> %d\n", u, v);
#endif
NT[u].e = new EdgeT(&NT[u], &NT[v]);
NT[v].deg++;
}
namespace TopoSort {
void dfs(NodeT *u) {
u->vis = false;
for (EdgeT *e = u->e; e; e = e->next) if (e->v->vis) dfs(e->v);
}
void findCircle(int n) {
std::stack<NodeT *> s;
for (int i = 1; i <= n; i++) {
if (NT[i].deg == 0) s.push(&NT[i]);
else NT[i].vis = false;
}
while (!s.empty()) {
NodeT *u = s.top();
s.pop();
u->vis = true;
for (EdgeT *e = u->e; e; e = e->next) {
e->v->deg--;
if (e->v->deg == 0) s.push(e->v);
}
}
// for (int i = 1; i <= n; i++) if (!NT[i].vis) dfs(&NT[i]);
}
}
int n, m;
int getID(int x, int y) {
return (x - 1) * m + y;
}
int score[MAXN * MAXM + 1], tot;
void rebuild() {
tot = 0;
const int s = 0, t = n * m + 1;
for (int i = 1; i <= getID(n, m); i++) {
if (!NT[i].vis) continue;
if (score[i] > 0) addEdge(s, i, score[i]), tot += score[i];
else addEdge(i, t, -score[i]);
for (EdgeT *e = NT[i].e; e; e = e->next) if (e->v->vis)
addEdge(e->v->id, i, INT_MAX);
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
int k;
#ifdef DBG
printf("(%d, %d)\n", i, j);
#endif
scanf("%d %d", &score[getID(i, j)], &k);
NT[getID(i, j)].id = getID(i, j);
while (k--) {
int x, y;
scanf("%d %d", &x, &y);
x++, y++;
addEdgeT(getID(i, j), getID(x, y));
}
if (j != 1) addEdgeT(getID(i, j), getID(i, j - 1));
}
TopoSort::findCircle(getID(n, m));
rebuild();
#ifdef DBG
printf("tot = %d\n", tot);
#endif
const int s = 0, t = n * m + 1;
printf("%d\n", tot - Dinic::solve(s, t, t + 1));
return 0;
}