发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是‘.‘，那么表示这是一块空地；如果是‘X‘，那么表示这是一面墙，如果是‘D‘，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符‘.‘、‘X‘和‘D‘，且字符间无空格。
只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出‘impossible‘（不包括引号）。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<iostream> 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 #define ll long long 7 #define dd double 8 using namespace std; 9 const int INF=(1<<31)-1; 10 inline int maxn(int a,int b){return a>b?a:b;} 11 inline int minn(int a,int b){return a<b?a:b;} 12 char readchar() 13 { 14 char q=getchar(); 15 while(q!=‘.‘&&q!=‘X‘&&q!=‘D‘)q=getchar(); 16 return q; 17 } 18 struct son 19 { 20 int u,v,next,w; 21 }; 22 son a1[1000001]; 23 int first[1000001],e; 24 25 void addbian(int u,int v,int w) 26 { 27 a1[e].v=v; 28 a1[e].w=w; 29 a1[e].u=u; 30 a1[e].next=first[u]; 31 first[u]=e++; 32 } 33 void Link(int u,int v,int w){addbian(u,v,w);addbian(v,u,0);} 34 int dui[10000001]; 35 int he,en; 36 inline void clear(){he=1;en=0;} 37 inline void pop(){++he;} 38 inline bool empty(){return en>=he?0:1;} 39 inline int top(){return dui[he];} 40 inline void push(int x){dui[++en]=x;} 41 42 int n,m,S,T,dmax,sumdoor; 43 int ha[56][56][506]; 44 int panduan; 45 char a[56][56]; 46 47 struct son1 48 { 49 int x,y,val; 50 }; 51 son1 ji[56][56][506]; 52 int num[56][56]; 53 54 queue<son1> q; 55 56 bool flag[56][56]; 57 void Bfs(int x,int y) 58 { 59 while(!q.empty())q.pop(); 60 mem(flag,0); 61 son1 now=(son1){x,y,0}; 62 q.push(now);flag[x][y]=1; 63 while(!q.empty()) 64 { 65 now=q.front();q.pop(); 66 //printf("%d %d %d\n",now.x,now.y,now.val); 67 if(a[now.x][now.y]==‘D‘){ji[x][y][++num[x][y]]=now;continue;} 68 //flag在push进来之后就要标记，不然你懂得 69 if(now.x>1&&!flag[now.x-1][now.y]&&a[now.x-1][now.y]!=‘X‘){q.push((son1){now.x-1,now.y,now.val+1});flag[now.x-1][now.y]=1;} 70 if(now.x<n&&!flag[now.x+1][now.y]&&a[now.x+1][now.y]!=‘X‘){q.push((son1){now.x+1,now.y,now.val+1});flag[now.x+1][now.y]=1;} 71 if(now.y>1&&!flag[now.x][now.y-1]&&a[now.x][now.y-1]!=‘X‘){q.push((son1){now.x,now.y-1,now.val+1});flag[now.x][now.y-1]=1;} 72 if(now.y<m&&!flag[now.x][now.y+1]&&a[now.x][now.y+1]!=‘X‘){q.push((son1){now.x,now.y+1,now.val+1});flag[now.x][now.y+1]=1;} 73 } 74 if(!num[x][y]) 75 panduan=1; 76 } 77 78 int dep[200006]; 79 int bfs() 80 { 81 mem(dep,0);clear(); 82 dep[S]=1;push(S); 83 while(!empty()) 84 { 85 int now=top();pop(); 86 //printf("now=%d\n",now); 87 for(int i=first[now];i!=-1;i=a1[i].next) 88 { 89 int temp=a1[i].v; 90 if(dep[temp]||!a1[i].w)continue; 91 dep[temp]=dep[now]+1; 92 push(temp); 93 if(temp==T)return 1; 94 } 95 } 96 return 0; 97 } 98 99 int dfs(int x,int val) 100 { 101 //printf("x=%d T=%d\n",x,T); 102 if(x==T)return val; 103 int val2=val,k; 104 for(int i=first[x];i!=-1;i=a1[i].next) 105 { 106 int temp=a1[i].v; 107 //printf("x=%d temp=%d\n",x,temp); 108 if(!a1[i].w||dep[temp]!=dep[x]+1||!val2)continue; 109 k=dfs(temp,minn(val2,a1[i].w)); 110 if(!k){dep[temp]=0;continue;} 111 a1[i].w-=k;a1[i^1].w+=k;val2-=k; 112 } 113 return val-val2; 114 } 115 116 int Dinic() 117 { 118 int ans=0; 119 //cout<<1; 120 while(bfs()) 121 { 122 //cout<<2; 123 ans+=dfs(S,INF); 124 } 125 return ans; 126 } 127 128 void chu() 129 { 130 mem(ha,0); 131 mem(a1,0); 132 mem(first,-1); 133 e=0; 134 } 135 136 int check(int time) 137 { 138 chu(); 139 140 int now=0,ren; 141 for(int i=1;i<=n;++i) 142 for(int j=1;j<=m;++j) 143 if(a[i][j]==‘.‘) 144 ha[i][j][0]=++now; 145 ren=now; 146 for(int i=1;i<=n;++i) 147 for(int j=1;j<=m;++j) 148 if(a[i][j]==‘D‘) 149 for(int k=1;k<=time;++k) 150 ha[i][j][k]=++now; 151 S=0;T=now+1; 152 //printf("ren=%d\n",ren); 153 for(int i=1;i<=ren;++i)Link(S,i,1); 154 for(int i=1;i<=n;++i) 155 for(int j=1;j<=m;++j) 156 if(a[i][j]==‘.‘) 157 for(int l=1;l<=num[i][j];++l) 158 for(int k=ji[i][j][l].val;k<=time;++k) 159 Link(ha[i][j][0],ha[ji[i][j][l].x][ji[i][j][l].y][k],1); 160 161 for(int i=1;i<=n;++i) 162 for(int j=1;j<=m;++j) 163 if(a[i][j]==‘D‘) 164 for(int k=1;k<=time;++k) 165 Link(ha[i][j][k],T,1); 166 //printf("now=%d\n",now); 167 //printf("e=%d\n",e); 168 return Dinic()==ren; 169 } 170 171 int er(int l,int r) 172 { 173 //printf("l=%d r=%d\n",l,r); 174 if(l==r) 175 return l; 176 int mid=(l+r)>>1; 177 if(check(mid)) 178 return er(l,mid); 179 else 180 return er(mid+1,r); 181 } 182 183 int main(){ 184 //freopen("1.txt","r",stdin); 185 //freopen("data6.in","r",stdin); 186 scanf("%d%d",&n,&m); 187 for(int i=1;i<=n;++i) 188 for(int j=1;j<=m;++j) 189 {a[i][j]=readchar();if(a[i][j]==‘D‘)++sumdoor;} 190 //cout<<0; 191 for(int i=1;i<=n;++i) 192 for(int j=1;j<=m;++j) 193 if(a[i][j]==‘.‘) 194 Bfs(i,j); 195 //printf("%d\n",ji[11][4].val); 196 //cout<<0; 197 //printf("dmax=%d\n",dmax); 198 //printf("ssss=%d %d\n",dmax,n*m+1); 199 if(panduan)puts("impossible"); 200 else 201 printf("%d",er(1,n*m+1)); 202 //while(1); 203 return 0; 204 }
原文：http://www.cnblogs.com/A-LEAF/p/7260612.html
