紧急疏散evacuate

1689: [HNOI2007]紧急疏散evacuate

题目描述

发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是"."，那么表示这是一块空地；如果是"X"，那么表示这是一面墙，如果是"D"，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

输入

输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符"."、"X"和"D"，且字符间无空格。

输出

只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出"impossible"（不包括引号）。

样例输入

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

样例输出

3



　　一道网络流的题：我们发现时间是满足单调性的，所以可以二分时间logn的复杂度，在当前时间限制下，将原点与每个人相连，每个人于能到达的不同时刻的每个门相连，意思是要将每个门拆点，拆成在不同时刻的门。所以要预处理出每个人到每个门的最短距离，跑一边dfs,再由这些门与汇点相连，这些边的容量为一；在这道题上炮最大流就行了，当且仅当最大流的数值等于总人数是，此时间点是可行的。
　　如果最终结果为你二分的上界的话：意思是没有这种情况，cout<<impossible；所以上界要定的稍大一些；


附代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<map>
  6 #include<queue>
  7 using namespace std;
  8 #define inf 5000000
  9 map<pair<int,int>,int>ma;
 10 int n,m,num,cnt,shu;
 11 int pos[21][21],id[21][21],dis[401][401];
 12 char s[21][21];int adj[10002];
 13 struct flow{
 14     int s,t,w,next;
 15 }k[2000001];
 16 int read(){
 17     int sum=0;char ch=getchar();
 18     while(ch<'0'||ch>'9') ch=getchar();
 19     while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
 20     return sum;
 21 }
 22 void dfs(int fa,int cnt,int x,int y){
 23     if(pos[x-1][y]==1){
 24         if(dis[fa][id[x-1][y]]>dis[fa][cnt]+1){    
 25             dis[fa][id[x-1][y]]=dis[fa][cnt]+1;
 26             dfs(fa,id[x-1][y],x-1,y);
 27         }
 28     }
 29     if(pos[x+1][y]==1){
 30         if(dis[fa][id[x+1][y]]>dis[fa][cnt]+1){
 31             dis[fa][id[x+1][y]]=dis[fa][cnt]+1;
 32             dfs(fa,id[x+1][y],x+1,y);
 33         }
 34     }
 35     if(pos[x][y-1]==1){
 36         if(dis[fa][id[x][y-1]]>dis[fa][cnt]+1){
 37             dis[fa][id[x][y-1]]=dis[fa][cnt]+1;
 38             dfs(fa,id[x][y-1],x,y-1);
 39         }
 40     }
 41     if(pos[x][y+1]==1){
 42         if(dis[fa][id[x][y+1]]>dis[fa][cnt]+1){
 43             dis[fa][id[x][y+1]]=dis[fa][cnt]+1;
 44             dfs(fa,id[x][y+1],x,y+1);
 45         }   
 46     }
 47 }
 48 void search(int x,int y){
 49     dis[id[x][y]][id[x][y]]=0;
 50     dfs(id[x][y],id[x][y],x,y);
 51 }
 52 void init(int s,int t,int w){
 53     k[num].s=s;k[num].t=t;k[num].w=w;
 54     k[num].next=adj[s];adj[s]=num++;
 55 }
 56 void build(int lim){
 57     num=0;memset(adj,-1,sizeof(adj));
 58     for(int i=1;i<=n;++i)
 59         for(int j=1;j<=m;++j){
 60             if(pos[i][j]==1)
 61                 init(0,id[i][j],1),init(id[i][j],0,0);
 62             if(pos[i][j]==2){
 63                 for(int u=1;u<=lim;++u)
 64                     init(ma[make_pair(id[i][j],u)],10000,1),init(10000,ma[make_pair(id[i][j],u)],0);
 65                 for(int u=1;u<=n;++u)
 66                     for(int p=1;p<=m;++p)
 67                         if(pos[u][p]==1)
 68                             for(int b=dis[id[i][j]][id[u][p]];b<=lim;++b)
 69                                 init(id[u][p],ma[make_pair(id[i][j],b)],1),init(ma[make_pair(id[i][j],b)],id[u][p],0);                      }
 70     }
 71 }
 72 int dp[10001];
 73 bool bfs(){
 74     memset(dp,0,sizeof(dp));
 75     queue<int>q; 
 76     q.push(0);dp[0]=1;
 77     while(!q.empty()){
 78         int o=q.front();q.pop();
 79         for(int i=adj[o];i!=-1;i=k[i].next){
 80             if(!k[i].w||dp[k[i].t]) continue;
 81             dp[k[i].t]=dp[o]+1;
 82             if(k[i].t==10000) return true;
 83             q.push(k[i].t);
 84         }
 85     }
 86     return false;   
 87 }
 88 int Dfs(int o,int fw){
 89     if(o==10000) return fw;
 90     int tmp=fw,u;
 91     for(int i=adj[o];i!=-1;i=k[i].next){
 92         if(!k[i].w||!tmp||dp[k[i].t]!=dp[o]+1) continue;
 93         u=Dfs(k[i].t,min(k[i].w,tmp));
 94         if(!u){
 95             dp[k[i].t]=0;continue;
 96         }
 97         k[i].w-=u;k[i^1].w+=u;tmp-=u;
 98     }
 99     return fw-tmp;
100 }
101 bool judge(int ti){
102     build(ti);
103     int ans=0;
104     while(bfs())
105         ans+=Dfs(0,inf);
106     if(ans==shu) return true;
107     else return false;  
108 }
109 int erfen(int l,int r){
110     if(l==r) return l;
111     int mid=(l+r)>>1;
112     if(judge(mid)) 
113         return erfen(l,mid);
114     else
115         return erfen(mid+1,r);
116 }
117 int main(){
118    // freopen("a.in","r",stdin);
119    // freopen("a.out","w",stdout);
120     n=read();m=read(); 
121     memset(adj,-1,sizeof(adj));
122     memset(pos,0x3f,sizeof(pos));
123     memset(dis,0x3f,sizeof(dis)); 
124     for(int i=1;i<=n;++i)    
125         scanf("%s",s[i]);
126     for(int i=1;i<=n;++i)
127         for(int j=1;j<=m;++j)
128             if(s[i][j-1]=='D')
129                 pos[i][j]=2,id[i][j]=++cnt;
130             else if(s[i][j-1]=='.')
131                 pos[i][j]=1,id[i][j]=++cnt,shu++;
132     cnt=n*m;
133     for(int i=1;i<=n;++i)
134         for(int j=1;j<=m;++j)
135             if(pos[i][j]==2)
136                 for(int u=1;u<=200;++u)  
137                     ma[make_pair(id[i][j],u)]=++cnt;
138     for(int i=1;i<=n;++i)
139         for(int j=1;j<=m;++j)
140             if(pos[i][j]==2)
141                 search(i,j);
142     int ans=erfen(0,200);
143     if(ans==200) printf("impossible"); 
144     else  printf("%d
",ans);
145     return 0;
146 }