BZOJ 1189: [HNOI2007]紧急疏散evacuate( BFS + 二分答案 + 匈牙利 )

时间：2022-11-21 07:08:30

BZOJ 1189: [HNOI2007]紧急疏散evacuate( BFS + 二分答案 + 匈牙利 )

我们可以BFS出每个出口到每个人的最短距离, 然后二分答案, 假设当前答案为m, 把一个出口拆成m个表示m个时间, 点u到出口v的距离为d, 那么u->v的[d, m]所有点连边, 然后跑匈牙利去check就行了...其实这道题挺好想但是码量还是挺大的....

-----------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
 
using namespace std;
 
#define chk(r, c) (r >= 0 && r < N && c >= 0 && c < M)
 
const int maxn = 29;
const int MAXN = 330;
const int MAX_V = 80;
const int INF = 0X3F3F3F3F;
const int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
 
struct edge {
int to;
edge* next;
} E[8000000], *pt, *head[MAXN];
 
void InitEdge() {
pt = E;
memset(head, 0, sizeof head);
}
 
void AddEdge(int u, int v) {
pt->to = v; pt->next = head[u]; head[u] = pt++;
}
 
int D[MAX_V][MAXN];
int R[MAXN], C[MAXN], _R[MAX_V], _C[MAX_V], Id[maxn][maxn];
int vis[MAXN * MAXN], mch[MAXN * MAXN];
int CK, N, M, V, _V;
char s[maxn][maxn];
queue<int> Q;
 
bool Dfs(int x) {
for(edge* e = head[x]; e; e = e->next) if(vis[e->to] != CK) {
vis[e->to] = CK;
if(!~mch[e->to] || Dfs(mch[e->to])) {
mch[e->to] = x;
return true;
}
}
return false;
}
 
void BFS(int x) {
memset(D[x], INF, sizeof D[x]);
while(!Q.empty()) Q.pop();
int X = _R[x], Y = _C[x];
if((X == N - 1 && Y == M - 1) || (!X && !Y)) return;
if(!X && ~Id[X + 1][Y]) {
Q.push(Id[X + 1][Y]);
D[x][Id[X + 1][Y]] = 0;
}
if(X == N - 1 && ~Id[X - 1][Y]) {
Q.push(Id[X - 1][Y]);
D[x][Id[X - 1][Y]] = 0;
}
if(!Y&& ~Id[X][Y + 1]) {
Q.push(Id[X][Y + 1]);
D[x][Id[X][Y + 1]] = 0;
}
if(Y == M - 1 && ~Id[X][Y - 1]) {
Q.push(Id[X][Y - 1]);
D[x][Id[X][Y - 1]] = 0;
}
while(!Q.empty()) {
int v = Q.front(); Q.pop();
int r = R[v], c = C[v];
for(int i = 0; i < 4; i++) {
int _r = r + dir[i][0], _c = c + dir[i][1];
if(!chk(_r, _c) || s[_r][_c] != '.') continue;
int _v = Id[_r][_c];
if(~_v && D[x][v] + 1 < D[x][_v]) {
D[x][_v] = D[x][v] + 1;
Q.push(_v);
}
}
}
}
 
void Init() {
memset(Id, -1, sizeof Id);
V = _V = 0;
scanf("%d%d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("%s", s[i]);
for(int j = 0; j < M; j++) switch(s[i][j]) {
case '.' : R[V] = i; C[V] = j; Id[i][j] = V++; break;
case 'D' : _R[_V] = i; _C[_V] = j; Id[i][j] = _V++; break;
default : break;
}
}
for(int i = 0; i < _V; i++) BFS(i);
}
 
void InitArray() {
memset(vis, -1, sizeof vis);
memset(mch, -1, sizeof mch);
}
 
bool Jud(int m) {
InitEdge();
InitArray();
for(int i = 0; i < _V; i++) {
int B = i * m;
for(int j = 0; j < V; j++)
for(int k = D[i][j]; k < m; k++)
AddEdge(j, B + k);
}
int cnt = 0;
for(CK = 0; CK < V; CK++)
if(Dfs(CK)) cnt++;
return cnt == V;
}
 
bool Imp() {
memset(vis, 0, sizeof vis);
for(int i = 0; i < _V; i++)
for(int j = 0; j < V; j++)
if(D[i][j] != INF) vis[j] = -1;
for(int i = 0; i < V; i++)
if(~vis[i]) return false;
return true;
}
 
int main() {
Init();
if(!Imp()) {
puts("impossible"); return 0;
}
int l = 1, r = V, ans = 0;
while(l <= r) {
int m = (l + r) >> 1;
if(Jud(m))
ans = m, r = m - 1;
else
l = m + 1;
}
printf("%d\n", ans);
return 0;
}

-----------------------------------------------------------------------------

1189: [HNOI2007]紧急疏散evacuate

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1219  Solved: 448
[Submit][Status][Discuss]

Description

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

Input

输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D'，且字符间无空格。

Output

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

Sample Input

5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX

Sample Output

3

HINT

Source

相关文章