标签：网络流，dinic，二分，最大流
题目
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 5 5
XXXXX
X…D
XX.XX
X..XX
XXDXX Sample Output 3 HINT
2015.1.12新加数据一组，鸣谢1756500824
C++语言请用scanf(“%s”,s)读入！
分析
首先每个门做一次bfs，求这扇门到每一个人的时间，然后二分时间T，跑最大流dinic算法，如果流量=人数那么T就是一个可行的答案
具体的建图操作如下：
- 从源点向每个空地连一条流量为1的边
- 每个门向汇点连一条流量为T的边
- 每个空地向可以到达的门连一条流量为T的边
code
本代码目前无法在BZOJ上AC，wxh大爷太毒瘤了，加强的一组数据强悍
4 5 XXDXX XX.XX X…X XXDXX
ans=3
luogu数据较弱，可以AC，话说我要不要去加强下luogu的数据啊，逃）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},maxn=1e3+6,S=0,T=1001;
int n,m,door=1,cnt,ans,tot,na=-1;
int Map[26][26],last[maxn],h[maxn],que[maxn];
int dis[406][26][26];
char ch[26];
struct node{int x,y,s;}d[maxn];
struct edge{int to,next,v;}e[maxn*maxn];
void insert(int u,int v,int w){
e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
bool bfs()
{
int head=0,tail=1,now;
mem(h,-1);h[S]=0;que[0]=S;
while(head<tail){
now=que[head++];
reg(now)
if(h[e[i].to]==-1&&e[i].v){
h[e[i].to]=h[now]+1;
que[tail++]=e[i].to;
}
}
return h[T]!=-1;
}
int dfs(int x,int f){
if(x==T)return f;
int w,used=0;
reg(x)
if(h[e[i].to]==h[x]+1){
w=dfs(e[i].to,min(e[i].v,f-used));
e[i].v-=w,e[i^1].v+=w,used+=w;
if(used==f)return f;
}
if(!used)h[x]=-1;
return used;
}
void dinic(){while(bfs())ans+=dfs(0,inf);}
void build(int x){
mem(last,0);cnt=1;
rep(i,1,n)
rep(j,1,m)if(Map[i][j]==1)insert(S,(i-1)*m+j,1);
rep(i,2,door)insert(n*m+i,T,x);
rep(i,2,door)
rep(j,1,n)
rep(k,1,m)
if(dis[i][j][k]<=x)insert((j-1)*m+k,n*m+i,x);
}
bool judge(int x){
build(x);ans=0;dinic();if(ans==tot)return 1;return 0;
}
void search(int k,int x,int y){
int head=0,tail=1,nx,ny;
d[0].x=x,d[0].y=y;
while(head<tail){
rep(i,0,3){
nx=d[head].x+dx[i],ny=d[head].y+dy[i];
if(nx<1||ny<1||nx>n||ny>m||Map[nx][ny]!=1)continue;
if(dis[k][nx][ny]==inf){
dis[k][nx][ny]=d[tail].s=d[head].s+1;
d[tail].x=nx,d[tail++].y=ny;
}
}
head++;
}
}
int main()
{
n=read(),m=read();
rep(i,1,n){
scanf("%s",ch);
rep(j,1,m){
if(ch[j-1]=='.')Map[i][j]=1,tot++;
else if(ch[j-1]=='D')Map[i][j]=++door;
}
}
rep(i,2,door)
rep(j,1,n)
rep(k,1,m)dis[i][j][k]=inf;
rep(i,1,n)
rep(j,1,m)
if(Map[i][j]>1)search(Map[i][j],i,j);
int l=0,r=406;
while(l<=r){
int mid=(l+r)>>1;
if(judge(mid))na=mid,r=mid-1;
else l=mid+1;
}
//cout<<l<<' '<<r<<endl;
if(na==-1)printf("impossible");
else printf("%d\n",na);
return 0;
}
