[BZOJ 1189][HNOI 2007] 紧急疏散

题目大意

假设每个房间是一个 \(N \times M\) 的矩形区域。每个格子如果是 . ,那么表示这是一块空地;如果是 X,那么表示这是一面墙,如果是 D,那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散时,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上可以同时站无数个人。但是,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。

如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。

\(3 \leqslant N, \ M \leqslant 20\)

题目链接

BZOJ 1189

CodeVS 3566

题解

二分答案 + 网络流判断可行。

在建图的时候,要注意一些细节。对于要检查的时间 \(t\),我们对于每一个空地,从源点向其建一条容量为 \(1\) 的边;对于每一个门,拆成 \(t\) 个点,每一个点向汇点建一条容量为 \(1\) 的边;对于每一个空地,向此时它能到的门的对应时间的点建一条容量为 \(1\) 的边(要向最早到达时间及以后时间的点连边,最短时间可由 bfs 求得),跑一遍最大流就是时间 \(t\) 下最多能逃离的人数。网上我看到的大部分题解在建图时都没有对门拆点,而是直接从门向汇点建一条容量为\(t\)的边,这种方法用下面这个数据就能叉掉:

1
2
3
4
5
4 5
XXDXX
XX.XX
X...X
XXDXX

这组数据的答案为 \(3\),用不拆点的方法建图得到的答案是 \(2\)。。。

代码

对点的编号纠结了相当长的时间,之后又由于码力太差,调了一下午。。。

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
156
157
158
159
160
161
162
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>
// #define DBG
const int MAXN = 20;
int g[MAXN + 1][MAXN + 1];
struct Edge;
struct Node {
std::vector<Edge *> E;
std::vector<Edge *>::iterator currEdge;
int level;
} N[2 + MAXN * MAXN + MAXN * MAXN * MAXN * MAXN];
struct Edge {
Node *u, *v;
Edge *revEdge;
int cap, flow;
Edge(Node *u, Node *v, int cap) : u(u), v(v), cap(cap), flow(0) {}
};
void addEdge(int u, int v, int cap = 1) {
#ifdef DBG
printf("edge: %d --> %d\n", u, v);
#endif
Edge *a = new Edge(&N[u], &N[v], cap);
Edge *b = new Edge(&N[v], &N[u], 0);
a->revEdge = b;
b->revEdge = a;
N[u].E.push_back(a);
N[v].E.push_back(b);
}
struct Dinic {
bool makeLevelGraph(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) N[i].level = 0;
s->level = 1;
std::queue<Node *> q;
q.push(s);
while (!q.empty()) {
Node *u = q.front();
q.pop();
for (std::vector<Edge *>::iterator it = u->E.begin(); it != u->E.end(); it++) {
Edge *e = *it;
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 (std::vector<Edge *>::iterator &it = s->currEdge; it != s->E.end(); it++) {
Edge *e = *it;
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->revEdge->flow -= flow;
return flow;
}
}
}
return 0;
}
int operator()(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].currEdge = N[i].E.begin();
int flow = 0;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}
return res;
}
} dinic;
int n, m;
struct Point {
int x, y, d;
Point(int x, int y, int d) : x(x), y(y), d(d) {}
};
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int dist[MAXN * MAXN + 2][MAXN + 1][MAXN + 1], people, door = 1;
bool isValid(const Point &p) {
return p.x >= 1 && p.x <= n && p.y >= 1 && p.y <= m && g[p.x][p.y] == 1;
}
void search(int k, int x, int y) {
std::queue<Point> q;
q.push(Point(x, y, 0));
while (!q.empty()) {
Point u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
Point v(u.x + dx[i], u.y + dy[i], 0);
if (!isValid(v)) continue;
if (dist[k][v.x][v.y] == INT_MAX) {
dist[k][v.x][v.y] = u.d + 1;
q.push(Point(v.x, v.y, u.d + 1));
}
}
}
}
void clear(int n) {
for (int i = 0; i < n; i++) N[i].E.clear();
}
void build(int N, int T, int s, int t) {
clear(N);
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
if (g[i][j] == 1) addEdge(s, (i - 1) * m + j);
}
for (int i = n * m + 1; i < t; i++) addEdge(i, t);
for (int i = 2; i <= door; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= m; k++) for (int l = dist[i][j][k]; l <= T; l++)
addEdge((j - 1) * m + k, n * m + (door - 1) * (l - 1) + i - 1);
}
bool check(int T) {
#ifdef DBG
printf("check(%d)\n", T);
#endif
int N = 2 + n * m + (door - 1) * T;
int s = 0, t = N - 1;
build(N, T, s, t);
int flow = dinic(s, t, N);
#ifdef DBG
printf("check(%d): flow = %d\n", T, flow);
#endif
if (flow == people) return true;
else return false;
}
int dichotomy() {
int l = 0, r = m * n;
int res = -1;
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) res = mid, r = mid;
else l = mid + 1;
}
return res;
}
int main() {
scanf("%d %d", &n, &m);
char str[MAXN + 1];
for (int i = 1; i <= n; i++) {
scanf("%s", str + 1);
for (int j = 1; j <= m; j++) {
if (str[j] == '.') g[i][j] = 1, people++;
else if (str[j] == 'D') g[i][j] = ++door;
}
}
for (int i = 2; i <= door; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= m; k++) dist[i][j][k] = INT_MAX;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (g[i][j] > 1) search(g[i][j], i, j);
#ifdef DBG
for (int i = 2; i <= door; i++) {
printf("Door : %d\n", i - 1);
for (int j = 1; j <= n; j++) for (int k = 1; k <= m; k++)
printf("dist[%d][%d][%d] = %d%c", i, j, k, dist[i][j][k], k == m ? '\n' : ' ');
}
#endif
int ans = dichotomy();
if (ans == -1) puts("impossible");
else printf("%d\n", ans);
return 0;
}