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；所以上界要定的稍大一些； 附代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
#define inf 5000000
map<pair<int,int>,int>ma;
int n,m,num,cnt,shu;
int pos[][],id[][],dis[][];
char s[][];int adj[];
struct flow{
int s,t,w,next;
}k[];
int read(){
int sum=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<=''){sum=sum*+ch-'';ch=getchar();}
return sum;
}
void dfs(int fa,int cnt,int x,int y){
if(pos[x-][y]==){
if(dis[fa][id[x-][y]]>dis[fa][cnt]+){
dis[fa][id[x-][y]]=dis[fa][cnt]+;
dfs(fa,id[x-][y],x-,y);
}
}
if(pos[x+][y]==){
if(dis[fa][id[x+][y]]>dis[fa][cnt]+){
dis[fa][id[x+][y]]=dis[fa][cnt]+;
dfs(fa,id[x+][y],x+,y);
}
}
if(pos[x][y-]==){
if(dis[fa][id[x][y-]]>dis[fa][cnt]+){
dis[fa][id[x][y-]]=dis[fa][cnt]+;
dfs(fa,id[x][y-],x,y-);
}
}
if(pos[x][y+]==){
if(dis[fa][id[x][y+]]>dis[fa][cnt]+){
dis[fa][id[x][y+]]=dis[fa][cnt]+;
dfs(fa,id[x][y+],x,y+);
}
}
}
void search(int x,int y){
dis[id[x][y]][id[x][y]]=;
dfs(id[x][y],id[x][y],x,y);
}
void init(int s,int t,int w){
k[num].s=s;k[num].t=t;k[num].w=w;
k[num].next=adj[s];adj[s]=num++;
}
void build(int lim){
num=;memset(adj,-,sizeof(adj));
for(int i=;i<=n;++i)
for(int j=;j<=m;++j){
if(pos[i][j]==)
init(,id[i][j],),init(id[i][j],,);
if(pos[i][j]==){
for(int u=;u<=lim;++u)
init(ma[make_pair(id[i][j],u)],,),init(,ma[make_pair(id[i][j],u)],);
for(int u=;u<=n;++u)
for(int p=;p<=m;++p)
if(pos[u][p]==)
for(int b=dis[id[i][j]][id[u][p]];b<=lim;++b)
init(id[u][p],ma[make_pair(id[i][j],b)],),init(ma[make_pair(id[i][j],b)],id[u][p],); }
}
}
int dp[];
bool bfs(){
memset(dp,,sizeof(dp));
queue<int>q;
q.push();dp[]=;
while(!q.empty()){
int o=q.front();q.pop();
for(int i=adj[o];i!=-;i=k[i].next){
if(!k[i].w||dp[k[i].t]) continue;
dp[k[i].t]=dp[o]+;
if(k[i].t==) return true;
q.push(k[i].t);
}
}
return false;
}
int Dfs(int o,int fw){
if(o==) return fw;
int tmp=fw,u;
for(int i=adj[o];i!=-;i=k[i].next){
if(!k[i].w||!tmp||dp[k[i].t]!=dp[o]+) continue;
u=Dfs(k[i].t,min(k[i].w,tmp));
if(!u){
dp[k[i].t]=;continue;
}
k[i].w-=u;k[i^].w+=u;tmp-=u;
}
return fw-tmp;
}
bool judge(int ti){
build(ti);
int ans=;
while(bfs())
ans+=Dfs(,inf);
if(ans==shu) return true;
else return false;
}
int erfen(int l,int r){
if(l==r) return l;
int mid=(l+r)>>;
if(judge(mid))
return erfen(l,mid);
else
return erfen(mid+,r);
}
int main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
n=read();m=read();
memset(adj,-,sizeof(adj));
memset(pos,0x3f,sizeof(pos));
memset(dis,0x3f,sizeof(dis));
for(int i=;i<=n;++i)
scanf("%s",s[i]);
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
if(s[i][j-]=='D')
pos[i][j]=,id[i][j]=++cnt;
else if(s[i][j-]=='.')
pos[i][j]=,id[i][j]=++cnt,shu++;
cnt=n*m;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
if(pos[i][j]==)
for(int u=;u<=;++u)
ma[make_pair(id[i][j],u)]=++cnt;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
if(pos[i][j]==)
search(i,j);
int ans=erfen(,);
if(ans==) printf("impossible");
else printf("%d\n",ans);
return ;
}