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

时间: 11-30

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

BZOJ 1189 HNOI2007 紧急疏散evacuate 二分答案+最大流

题目大意:给定一个m*n的地图,每个点有可能是空地.墙或者出口,每个空地初始站着一个人,每一时刻可以向周围走1格,门每一时刻只能通过一个人,求最短多少时间后所有人可以撤离 首先从每个出口出发开始广搜,得到每个空地到所有出口的距离 然后二分答案,每次建图如下: 从源点向每个空地一条流量为1的边 如果一个空地能在规定时间到达某个出口,就从这个空地出发向该出口链接一条流量为1的边 每个出口向汇点连接一条流量为时间的边 然后跑最大流验证即可 注意图有不连通的情况 所以广搜要清初值(这个没人会忘吧QAQ

【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',那么表示这是一扇门,人们可以从这儿撤出房间.已知门一定在房间的边界上,并且边界上不会有空地.最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动.疏散开始后,每块空地上就没有人数限制了(也就