1189: [HNOI2007]紧急疏散evacuate
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1155 Solved: 420
[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
XXXXX
X...D
XX.XX
X..XX
XXDXX
Sample Output
3
思路：
我是用二分匹配AC的，若从门走不可以走到所有空地，那么输出impossible，否则一定可以走出去。假设一个人走到门A处最少用时s，那么这个人可以从门A出去的时间为s、s+1、s+2等，由于每秒只能从一个门走出一个人，那么就是匹配关系了，左边是人，右边是在时间1s、2s、3s等时的门，从小到大匹配，当时间t时达到最大匹配则最少时间为t。
在网上看别人代码，大多数是最大流，st连所有人，流量1，所有人连在时间t内可以走到的门，流量1，所有门连end，流量t，二分t即可。
好像所有二分图都可以转化成网络流？？。。
二分匹配代码（网络流没敲不贴了）：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std; #define N 25
#define inf 999999999 int n, m;
char map[N][N];
int c[N][N]; struct node{
int x, y, d;
node(){}
node(int a,int b,int c){
x=a;y=b;d=c;
}
}a[N*]; struct dd{
int id, dis;
dd(){ }
dd(int a,int b){
id=a;dis=b;
}
}b[N*][]; bool cmp(dd a,dd b){
return a.dis<b.dis;
} int xx[]={,-,,};
int yy[]={,,,-};
bool visited[N][N];
bool V[N][N]; void bfs(int id){
queue<node>Q;
Q.push(a[id]);
memset(visited,false,sizeof(visited));
visited[a[id].x][a[id].y]=true;
node p, q;
int i;
int cnt=;
while(!Q.empty()){
p=Q.front();Q.pop();
for(i=;i<;i++){
q.x=p.x+xx[i];
q.y=p.y+yy[i];
if(q.x>=&&q.x<n&&q.y>=&&q.y<m&&map[q.x][q.y]=='.'&&!visited[q.x][q.y]){
q.d=p.d+;
Q.push(q);
b[id][cnt++]=dd(c[q.x][q.y],q.d);
V[q.x][q.y]=visited[q.x][q.y]=true;
}
}
}
} bool vis[];
int from[];
vector<int>ve[]; int march(int u){
int i, v;
for(i=;i<ve[u].size();i++){
v=ve[u][i];
if(!vis[v]){
vis[v]=true;
if(from[v]==-||march(from[v])){
from[v]=u;
return ;
}
}
}
return ;
} main()
{
int i, j, k;
while(scanf("%d %d",&n,&m)==){
for(i=;i<n;i++) scanf("%s",map[i]);
int temp=, cnt=;
for(i=;i<n;i++){
for(j=;j<m;j++){
if(map[i][j]=='.'){
c[i][j]=temp++;
}
else if(map[i][j]=='D'){
a[cnt++]=node(i,j,);
}
}
}
memset(V,false,sizeof(V));
for(i=;i<cnt;i++){
bfs(i);
}
int ff=;
for(i=;i<n;i++){
for(j=;j<m;j++){
if(!V[i][j]&&map[i][j]=='.'){
ff=;
}
}
}
if(!ff){
printf("impossible\n");continue;
}
for(i=;i<cnt;i++) sort(b[i],b[i]+temp,cmp);
for(i=;i<temp;i++) ve[i].clear();
int t=;
while(){
for(i=;i<cnt;i++){
for(j=;j<temp;j++){
if(b[i][j].dis<=t){
ve[b[i][j].id].push_back(i+cnt*(t-));
}
else break;
}
}
memset(from,-,sizeof(from));
int f=;
for(i=;i<temp;i++){
memset(vis,false,sizeof(vis));
if(!march(i)){
f=;break;
}
}
if(f) break;
t++;
}
printf("%d\n",t);
}
}