[文章目录]
Description
发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。3<=N <=20，3<=M<=20
门每秒只能过一个人比较头疼，那么就对于每个时间建一个点。
每个门bfs到可及平地的最短路，之后动态加边网络流，将时间拆点，每个door拆时间个点，时间i向时间i+1连边，流量为inf，平地向对应时间连边，流量为1，s向平地连边，流量为1，每个时间向t连边，流量为1，满流即为解。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 410
const int inf=0x3f3f3f3f;
int n,m,s,t,di,num,pd[N],d[N],rt[N];
char mp[30][30];
struct node
{
int a,b,w;
}ed[40000];
bool cmp(node x,node y){return x.w<y.w;}
bool vis[30][30];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void bfs_dis(int x,int y)
{
memset(vis,0,sizeof vis);
static int qx[N],qy[N],qd[N];
int l=1,r=1; vis[x][y]=1; qx[1]=x; qy[1]=y; qd[1]=0;
int z,xx,yy,id=(x-1)*m+y;
while(l<=r)
{
x=qx[l]; y=qy[l]; z=qd[l]; ++l;
for(int i=0;i<4;++i)
{
xx=x+dx[i]; yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]=='.'&&!vis[xx][yy])
{
vis[xx][yy]=1;
++r; qx[r]=xx; qy[r]=yy; qd[r]=z+1;
++num; ed[num].a=(xx-1)*m+yy; ed[num].b=id; ed[num].w=z+1;
}
}
}
}
int head[N*N],to[500000],nxt[500000],f[500000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[N*N];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0 ;q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(tmp,f[i]));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m); s=0; t=n*m+1; di=t;
for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
int tot=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
++tot;
if(mp[i][j]=='.') pd[++pd[0]]=tot;
if(mp[i][j]=='D') d[++d[0]]=tot,bfs_dis(i,j);
}
}
sort(ed+1,ed+num+1,cmp);
for(int i=pd[0];i;--i) add(s,pd[i],1);
tot=ed[num].w;
int tmp=0,ans,now=1;
for(int i=0;i<=tot+n*m;++i)
{
for(int j=1;j<=d[0];++j)
{
if(i!=0) add(rt[d[j]],di+1,inf);
rt[d[j]]=++di; add(di,t,1);
}
while(now<=num&&ed[now].w<=i) add(ed[now].a,rt[ed[now].b],1),++now;
while(bfs()) tmp+=dinic(s,inf);
if(tmp==pd[0]) {ans=i; break;}
}
if(tmp==pd[0]) printf("%d",ans);
else puts("impossible");
return 0;
}