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

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

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

void InitEdge() {

pt = E;

}

void AddEdge(int u, int v) {

}

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++)

}

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]

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

3

## 【BZOJ】1189: [HNOI2007]紧急疏散evacuate（二分+bfs+网络流）

http://www.lydsy.com/JudgeOnline/problem.php?id=1189 表示完全不会QAQ.... 于是膜拜题解orz 二分时间........... 于是转换成判定性问题:即如何在有限时间内通过. 假设当前有t时间可供通过...那么每一个门最多能通过t个人........ 然后将所有能够到达门的点连边,容量为无限.... 然后源向每个点可行点连边..容量1.. 然后每个门向汇连边..容量为t.. 然后判断即可.... (一开始bfs写错了啊QAQ.. #inc

## BZOJ 1189 [HNOI2007]紧急疏散evacuate

Description 发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域.每个格子如果是'.',那么表示这是一块空地:如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间.已知门一定在房间的边界上,并且边界上不会有空地.最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动.疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人).但是,由于门很窄,每一秒钟只能有

## 1189. [HNOI2007]紧急疏散EVACUATE【最大流+枚举或二分】

Description 发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域.每个格子如果是'.',那么表示这是一 块空地:如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间.已知门 一定在房间的边界上,并且边界上不会有空地.最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都 可以向上下左右四个方向移动一格,当然他也可以站着不动.疏散开始后,每块空地上就没有人数限制了(也就是 说每块空地可以同时站无数个人).但是,由于门很窄,每一秒

## bzoj千题计划132：bzoj1189: [HNOI2007]紧急疏散evacuate

http://www.lydsy.com/JudgeOnline/problem.php?id=1189 二分答案 源点向人连边,流量为1 门拆为mid个点,同一个门的第j个点向第j+1个点连边,流量为inf 若第i个人第k秒到达第j个门,第i个人向第j个门拆出的第k个点连边,流量为1 所有门向汇点连边,流量为1 用ISAP写的,真快,也真TM长 #include<queue> #include<cstdio> #include<algorithm> #include&

## BZOJ1189: [HNOI2007]紧急疏散evacuate 二分+最大流

1189: [HNOI2007]紧急疏散evacuate Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1132  Solved: 412[Submit][Status][Discuss] Description 发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域.每个格子如果是'.',那么表示这是一块空地:如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间.已知门一定在房间的边界上,并且

## AC日记——[HNOI2007]紧急疏散evacuate bzoj 1189

[HNOI2007]紧急疏散evacuate 思路: 处理每个人到门的最短路: 然后二分答案: s向人连边流量1: 人向门拆分后的点连边流量1(拆成400,前一个点连当前点流量INF): 然后门向t连边流量二分的答案: 如果最后流量等于人的个数,则true: 来,上代码: #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorit

## [HNOI2007]紧急疏散EVACUATE （湖南2007年省选）

[HNOI2007]紧急疏散EVACUATE 题目描述 发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域.每个格子如果是'.',那么表示这是一块空地:如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间.已知门一定在房间的边界上,并且边界上不会有空地.最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动.疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人).

## 【BZOJ1189】[HNOI2007]紧急疏散evacuate 动态加边网络流

[BZOJ1189][HNOI2007]紧急疏散evacuate Description 发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域.每个格子如果是'.',那么表示这是一块空地:如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间.已知门一定在房间的边界上,并且边界上不会有空地.最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动.疏散开始后,每块空地上就没有人数限制了(也就