发生了火警，所有人员需要紧急疏散！假设每个房间是一个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\n",ans); 145 return 0; 146 }
原文：http://www.cnblogs.com/Maplers/p/7261196.html