BZOJ1189【HNOI2007】紧急疏散evacuate <二分答案+网络流>

Problem

【HNOI2007】紧急疏散evacuate


Description

发生了火警,所有人员需要紧急疏散!假设每个房间是一个 的矩形区域。每个格子如果是’ ’,那么表示这是一块空地;如果是’ ’,那么表示这是一面墙,如果是’ ’,那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。

Input

输入文件第一行是由空格隔开的一对正整数 ,以下 列描述一个 的矩阵。其中的元素可为字符’ ’, ‘ ’和’ ’,且字符间无空格。

Output

只有一个整数K,表示让所有人安全撤离的最短时间,如果不可能撤离,那么输出’ ’(不包括引号)。

Sample Input

1
2
3
4
5
6
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX

Sample Output

1
3

HINT

2015.1.12新加数据一组,鸣谢1756500824
语言请用scanf("%s",s)读入!

标签:二分答案 网络流

Solution

这题真坑逼,调了两小时。坑点已用红色加粗。

首先我们可以很容易地想到需要以每个门为起点 ,记录每个点到每个门的距离是多少。然后二分答案,对于当前答案 ,建图如下:
从源点向每个有人的点连容量为 的边,从每个门向汇点连容量为 的边。然后对于每个人,枚举每个门,如果这个人到某个门的距离小于等于 ,那么这个人一定会在 时限内到达这个门前,所以我们从这个人向这个门连一条容量为 的边。跑一遍最大流,如果流量等于人数,则可行。
写出来就是这样:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define MAX_N 500
#define MAX_M 400000
#define INF 2147483647
using namespace std;
int n, m, s, t, id[20][20], ind, tot, num, pre[MAX_N+5], cnt; char map[20][20];
vector <int> G[MAX_N+5], exi; int dis[MAX_N+5][MAX_N+5]; bool vis[MAX_N+5];
int nxt[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct node {int v, c, nxt;} E[MAX_M+5];
void init() {cnt = 0; s = 0, t = n*m+1; memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c) {
E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;
E[cnt].v = u, E[cnt].c = 0, E[cnt].nxt = pre[v], pre[v] = cnt++;
}
char gc(int x) {return map[(x-1)/m][(x-1)%m];}
void BFS(int beg, int k) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n*m; i++) dis[i][k] = INF;
queue <int> que; dis[beg][k] = 0, que.push(beg), vis[beg] = true;
while (!que.empty()) {
int u = que.front(); que.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i]; if (vis[v] || gc(v) != '.') continue;
dis[v][k] = dis[u][k]+1, que.push(v), vis[v] = true;
}
}
}
int d[MAX_N+5];
bool BFS() {
memset(d, -1, sizeof(d));
queue <int> que; que.push(s), d[s] = 0;
while (!que.empty()) {
int u = que.front(); que.pop();
for (int i = pre[u]; ~i; i = E[i].nxt) {
int v = E[i].v; if (~d[v] || !E[i].c) continue;
d[v] = d[u]+1, que.push(v);
}
}
return ~d[t];
}
int DFS(int u, int flow) {
if (u == t) return flow;
int ret = 0;
for (int i = pre[u]; ~i; i = E[i].nxt) {
int v = E[i].v, c = E[i].c;
if (d[v] != d[u]+1 || !c) continue;
int tmp = DFS(v, min(flow, c));
E[i].c -= tmp, E[i^1].c += tmp, flow -= tmp, ret += tmp;
if (!flow) break;
}
if (!ret) d[u] = -1;
return ret;
}
bool check(int tans) {
init();
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '.') insert(s, id[i][j], 1);
for (int k = 0; k < exi.size(); k++) insert(exi[k], t, tans);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '.')
for (int k = 0; k < exi.size(); k++) if (dis[id[i][j]][k] <= tans)
insert(id[i][j], exi[k], 1);
int ret = 0;
while (BFS()) ret += DFS(s, INF);
return ret == num;
}
int bi_search(int l, int r) {
int ret;
while (l <= r) {
int mid = l+r>>1;
if (check(mid)) ret = mid, r = mid-1;
else l = mid+1;
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) id[i][j] = ++ind;
for (int i = 0; i < n; i++) scanf("%s", map[i]);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < 4; k++) {
int x = i+nxt[k][0], y = j+nxt[k][1];
if (x < 0 || x >= n || y < 0 || y >= m || map[i][j] == 'X' || map[x][y] == 'X') continue;
G[id[i][j]].push_back(id[x][y]);
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '.') num++;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == 'D') exi.push_back(id[i][j]);
for (int i = 0; i < exi.size(); i++) BFS(exi[i], i);
int ans = bi_search(0, m*n);
if (ans < m*n) printf("%d", ans);
else printf("impossible");
return 0;
}

然而 掉了。
原因很简单:某位神犇出了一组数据:

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

ans=3

然而用刚刚的方法做答案是
这是因为 都在 时刻到达 的门前,两个人分别过需要多一秒钟。
~
这里我们需要另一种建模方式:
首先源点向所有人连容量为 的边,然后把每个门拆成 个点,如果某人到某门的时间为 ,则从这个人向这个人的第 个点都连容量为 的边。最后把每个门的 个点向汇点连容量为 的边即可。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define MAX_N 50000
#define MAX_M 1000000
#define INF 2147483647
using namespace std;
int n, m, s, t, id[20][20], ind, tot, num, pre[MAX_N+5], cnt; char map[20][20];
vector <int> G[MAX_N+5], exi; int dis[MAX_N+5][500]; bool vis[MAX_N+5];
int nxt[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct node {int v, c, nxt;} E[MAX_M+5];
void init() {cnt = 0; s = 0, t = MAX_N; memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c) {
E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;
E[cnt].v = u, E[cnt].c = 0, E[cnt].nxt = pre[v], pre[v] = cnt++;
}
char gc(int x) {return map[(x-1)/m][(x-1)%m];}
void BFS(int beg, int k) {
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n*m; i++) dis[i][k] = INF;
queue <int> que; dis[beg][k] = 0, que.push(beg), vis[beg] = true;
while (!que.empty()) {
int u = que.front(); que.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i]; if (vis[v] || gc(v) != '.') continue;
dis[v][k] = dis[u][k]+1, que.push(v), vis[v] = true;
}
}
}
int d[MAX_N+5];
bool BFS() {
memset(d, -1, sizeof(d));
queue <int> que; que.push(s), d[s] = 0;
while (!que.empty()) {
int u = que.front(); que.pop();
for (int i = pre[u]; ~i; i = E[i].nxt) {
int v = E[i].v; if (~d[v] || !E[i].c) continue;
d[v] = d[u]+1, que.push(v);
}
}
return ~d[t];
}
int DFS(int u, int flow) {
if (u == t) return flow;
int ret = 0;
for (int i = pre[u]; ~i; i = E[i].nxt) {
int v = E[i].v, c = E[i].c;
if (d[v] != d[u]+1 || !c) continue;
int tmp = DFS(v, min(flow, c));
E[i].c -= tmp, E[i^1].c += tmp, flow -= tmp, ret += tmp;
if (!flow) break;
}
if (!ret) d[u] = -1;
return ret;
}
bool check(int tans) {
init();
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '.') insert(s, id[i][j], 1);
for (int k = 0; k < exi.size(); k++) for (int l = 1; l <= tans; l++) insert(n*m+l*exi.size()+k, t, 1);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '.')
for (int k = 0; k < exi.size(); k++) if (dis[id[i][j]][k] <= tans)
for (int l = dis[id[i][j]][k]; l <= tans; l++) insert(id[i][j], n*m+l*exi.size()+k, 1);
int ret = 0;
while (BFS()) ret += DFS(s, INF);
return ret == num;
}
int bi_search(int l, int r) {
int ret;
while (l <= r) {
int mid = l+r>>1;
if (check(mid)) ret = mid, r = mid-1;
else l = mid+1;
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) id[i][j] = ++ind;
for (int i = 0; i < n; i++) scanf("%s", map[i]);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < 4; k++) {
int x = i+nxt[k][0], y = j+nxt[k][1];
if (x < 0 || x >= n || y < 0 || y >= m || map[i][j] == 'X' || map[x][y] == 'X') continue;
G[id[i][j]].push_back(id[x][y]);
}
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '.') num++;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == 'D') exi.push_back(id[i][j]);
for (int i = 0; i < exi.size(); i++) BFS(exi[i], i);
int ans = bi_search(0, m*n);
if (ans < m*n) printf("%d", ans);
else printf("impossible");
return 0;
}

`

------------- Thanks For Reading -------------
0%