[HNOI2007]紧急疏散evacuate
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3626 Solved: 1059
[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
HINT
2015.1.12新加数据一组，鸣谢1756500824
题解：二分+二分图匹配吧，网络流可以，需要注意一下，一个时刻只能允许出去一个人，所以出口再裂几个点即可。
#include<cstdio>
const int M=,inf=0x3f3f3f3f;
int h[M],q[M],S,T;
int es[M],enx[M],ev[M],e0[M],ep=;
int n,m;
char s[][];
bool bfs(){
int ql=,qr=;
for(int i=;i<=T;i++)h[i]=;
h[S]=;
q[qr++]=S;
while(ql!=qr){
int w=q[ql++];
for(int i=e0[w];i;i=enx[i]){
if(!ev[i])continue;
int u=es[i];
if(h[u])continue;
h[u]=h[w]+;
q[qr++]=u;
}
}
return h[T];
}
int dfs(int w,int f){
if(w==T)return f;
int used=,c;
for(int i=e0[w];i;i=enx[i]){
if(!ev[i])continue;
int u=es[i];
if(h[u]!=h[w]+)continue;
c=f-used;
if(c>ev[i])c=ev[i];
c=dfs(u,c);
ev[i]-=c;
ev[i^]+=c;
used+=c;
if(f==used)return f;
}
if(f!=used)h[w]=;
return used;
}
void addedge(int a,int b,int f){
es[ep]=b;enx[ep]=e0[a];ev[ep]=f;e0[a]=ep++;
es[ep]=a;enx[ep]=e0[b];ev[ep]=;e0[b]=ep++;
}
int xs[]={-,,,};
int ys[]={,-,,};
int qx[],qy[],tag[][],len[][],now=;
bool chk(int X){
int pc=;
S=(n+)*m++X*n*m;T=S+;
for(int i=;i<=T;i++)e0[i]=;ep=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(s[i][j]=='.')addedge(S,i*m+j,),pc++;
if(s[i][j]=='D'){
for(int c=;c<=X;c++)addedge(i*m+j+c*n*m,T,);
int ql=,qr=;
qx[]=i;qy[]=j;qr++;
++now;
tag[i][j]=now;
len[i][j]=;
while(ql<qr){
int x=qx[ql],y=qy[ql];ql++;
if(s[x][y]=='.'&&len[x][y]<=X)for(int c=len[x][y];c<=X;c++)addedge(x*m+y,i*m+j+c*n*m,);
if(len[x][y]<=X)
for(int a=;a<;a++){
int x1=x+xs[a],y1=y+ys[a];
if((s[x1][y1]=='.')&&tag[x1][y1]!=now){
tag[x1][y1]=now;
len[x1][y1]=len[x][y]+;
qx[qr]=x1;qy[qr]=y1;qr++;
}
}
}
}
}
}
while(bfs())pc-=dfs(S,inf);
return !pc;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=;i++)for(int j=;j<=;j++)s[i][j]='X';
for(int i=;i<=n;i++){
scanf("%s",s[i]+);
s[i][m+]='X';
}
int L=,R=n*m+,M;
while(L<R){
M=L+R>>;
if(chk(M))R=M;
else L=M+;
}
while(!chk(L)&&L<=n*m)++L;
while(L>&&chk(L-))--L;
if(L<=n*m)printf("%d\n",L);
else puts("impossible");
return ;
}