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

Posted on Symbols count in article: 2.1k Reading time ≈ 8 mins.

Problem

【HNOI2007】紧急疏散evacuate

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

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

Input

输入文件第一行是由空格隔开的一对正整数NN与MM，3≤N≤203\le N\le 20，3≤M≤203\le M\le 20，以下NN行MM列描述一个N×MN\times M的矩阵。其中的元素可为字符’..', ‘XX’和’DD’，且字符间无空格。

Output

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

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
C++\mathrm{C++}语言请用scanf("%s",s)读入！

标签：二分答案 网络流

Solution

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

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

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;
}

然而WA\mathrm{WA}掉了。
原因很简单：某位神犇出了一组数据：

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

ans=3

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

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;
}