1189: [HNOI2007]紧急疏散evacuate
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
XXXXX
X...D
XX.XX
X..XX
XXDXX
Sample Output
这是一道二分+最大流的题。。。
先预处理出每个空地到每扇门的最短路(广搜妥妥的~)
再二分答案。。。
对于答案ti,将每扇门按时间拆成ti个点，
对于同一扇门有 i时刻的人可到 i+1时时刻再出去，
所以我们从 i时刻的点 连向 i+1时刻的点(容量无穷大)。。。
对于每个人，我们将其对应点 连向 到 Ta可到的门 的最小时刻(容量为1)。。。
从源点向每个人连边(容量为1)，从每扇门的每一时刻向汇点连边（容量也为1）。。。
有一个值得注意的细节，
如果人走到了门，就不能再走出门了。。。
蒟蒻wy悲伤地表示被这个细节坑了一下午。。。
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define MaxN 21
#define MaxP 401
#define MaxM 400010
#define MaxT 2000010
const int INF=0x3f3f3f3f;
int N,M,Dcnt,Pcnt,tot,S,T,Ans;
char s[MaxN];
int map[MaxN][MaxN],vis[MaxN][MaxN];
int dist[MaxP][MaxP];
int first[MaxM],next[MaxT],end[MaxT],cap[MaxT];
int lev[MaxM],cur[MaxM];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
struct point{
int x,y;
point(){}
point(int a,int b){
x=a; y=b;
}
int Num(){
return (x-1)*M+y;
}
}Door[MaxP],Person[MaxP];
queue <point> H;
queue <int> Q;
int Number(int x,int y){
return (x-1)*M+y;
}
void Bfs(point S){
int s=Number(S.x,S.y);
memset(vis,0x3f,sizeof(vis));
memset(dist[s],0x3f,sizeof(dist[s]));
dist[s][s]=vis[S.x][S.y]=0;
H.push(S);
for (;!H.empty();){
point u=H.front();
H.pop();
for (int i=0;i<4;++i){
int wx=u.x+xx[i];
int wy=u.y+yy[i];
if (wx< 0|| wx> N) continue;
if (wy< 0|| wy> M) continue;
if (! map[wx][wy]) continue;
if (map[wx][wy]&2) continue;
if (vis[wx][wy]> vis[u.x][u.y]+1){
dist[s][Number(wx,wy)]=vis[wx][wy]=vis[u.x][u.y]+1;
H.push(point(wx,wy));
}
}
}
}
void Add(int x,int y,int z){
next[++tot]=first[x]; first[x]=tot; end[tot]=y; cap[tot]=z;
next[++tot]=first[y]; first[y]=tot; end[tot]=x; cap[tot]=0;
}
void Build(int x){
S=0; T=Pcnt+Dcnt*x+1;
tot=1;
memset(first,0,sizeof(first));
for (int i=1;i<=Pcnt;++i) Add(S,i,1);
for (int i=1;i<=Dcnt;++i){
for (int ti=1;ti<=x;++ti) Add(Pcnt+(i-1)*x+ti,T,1);
for (int ti=1;ti<x;++ti) Add(Pcnt+(i-1)*x+ti,Pcnt+(i-1)*x+ti+1,INF);
int s=Door[i].Num(),tmp;
for (int pi=1;pi<=Pcnt;++pi)
if ((tmp=dist[s][Person[pi].Num()])<=x)
Add(pi,Pcnt+(i-1)*x+tmp,1);
}
}
bool Find(){
for (;!Q.empty();) Q.pop();
memset(lev+1,-1,sizeof(int)*T);
lev[S]=0;
cur[S]=first[S];
Q.push(S);
for (;!Q.empty();){
int u=Q.front();
Q.pop();
for (int k=first[u],v;v=end[k],k;k=next[k])
if (cap[k]&&lev[v]<0){
lev[v]=lev[u]+1;
cur[v]=first[v];
if (v==T) return true;
Q.push(v);
}
}
return false;
}
int Dinic(int u,int flow){
if (u==T) return flow;
int ans=0;
for (int &k=cur[u],v;v=end[k],k;k=next[k])
if (cap[k]&&lev[v]>lev[u]){
int tmp=Dinic(v,min(cap[k],flow-ans));
if (tmp){
cap[k]-=tmp;
cap[k^1]+=tmp;
ans+=tmp;
if (ans==flow) return flow;
}
}
if (ans!=flow) lev[u]=-1;
return ans;
}
bool Check(int x){
Build(x);
int ans=0;
for (;Find();)
ans+=Dinic(S,INF);
if (ans==Pcnt) return true;
return false;
}
int main(){
scanf("%d%d",&N,&M);
for (int i=1;i<=N;++i){
scanf("%s",s);
for (int j=0;j<M;++j){
map[i][j+1]= s[j]== 'X'? 0: (s[j]== 'D'? 2: 1);
if (map[i][j+1]&1) Person[++Pcnt]=point(i,j+1);
if (map[i][j+1]&2) Door[++Dcnt]=point(i,j+1);
}
}
for (int i=1;i<=Dcnt;++i) Bfs(Door[i]);
int l=1,r=800;
if (!Check(r)) printf("impossible\n");
else {
Ans=r;
for (;l<=r;){
int mid=(l+r)/2;
if (Check(mid)){
Ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",Ans);
}
}
评论 (0)
