题解 P3191 【[HNOI2007]紧急疏散EVACUATE】
Victorique · · 题解
真是奇怪这么恶心的网络流是怎么出现在这世界上的。。。（还有一个恶心的请见KOI这道题）
首先要求我们找一个最小逃出去的时间，那么我们就二分这个时间。那么如何把二分的这个时间和网络流结合起来呢？
首先我们可以考虑分层图，把这个图分成x层，然后把每一层的每个点向下一层连inf的边，然后如果某个点到某个门的距离是j，那么就在第j层给它连上一条边，流量为1。把第一层的起点和S相连，流量为1，所有的门（注意是每一层的都算），和T连边。然后DINIC判断其是否满足人数。
但是这样很明显不行。。。如果只有一个门，但是除了门其他地方全是人的话，这图建出来估计也完蛋了。。。
所以我们考虑减少边的数量，我们可以发现，我们把每一个点向下一层连的inf是没有必要的，对于第一层的每个人，我们枚举所有的门，看一下他能到达的最早的时间是什么时候，然后连一下就可以了。。。
那么我们如何处理每个人到达门的时间店呢？SPFA不可取，原因是，代码复杂度高还慢，不如你直接bfs每个点。然后，我因为实在太懒，用了flyod求最短路。。。如果想求速度的话不建议使用我的方法。。。但是基本没有什么代码的复杂度。。
注意每一次二分进去之后都要初始化数组。。
数组大小因人而异，这个题建图方式有很多，也不只我说的这一种。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define inf 400000000
#define id (i-1)*m+j
using namespace std;
struct po
{
int nxt,to,w;
}edge[3000021];
int head[100003],tot,dep[100003],num=-1,sum,n,cur[100001];
int m,s,t;
int idd[51][51],dis[501][501];
char map[501][501];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
inline int read()
{
int x=0,c=1;
char ch=' ';
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
while(ch=='-')c*=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x*c;
}
inline void add_edge(int from,int to,int w)
{
edge[++num].nxt=head[from];
edge[num].to=to;
edge[num].w=w;
head[from]=num;
}
inline void add(int from,int to,int w)
{
add_edge(from,to,w);
add_edge(to,from,0);
}
inline bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
while(!q.empty())
q.pop();
dep[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(re int i=head[u];i!=-1;i=edge[i].nxt){
int v=edge[i].to;
if(edge[i].w>0&&dep[v]==0){
dep[v]=dep[u]+1;
if(v==t) return 1;
q.push(v);
}
}
}
return 0;
}
inline int dfs(int u,int low)
{
if(u==t) return low;
int diss=0;
for(re int& i=cur[u];i!=-1;i=edge[i].nxt){
int v=edge[i].to;
if(edge[i].w!=0&&dep[v]==dep[u]+1){
int check=dfs(v,min(low,edge[i].w));
if(check){
low-=check;
diss+=check;
edge[i].w-=check;
edge[i^1].w+=check;
if(low==0) break;
}
}
}
return diss;
}
inline int dinic()
{
int ans=0;
while(bfs()){
for(re int i=s;i<=t;i++) cur[i]=head[i];
while(int d=dfs(s,inf))
ans+=d;
}
return ans;
}
inline bool check(int x)
{
memset(head,-1,sizeof(head));
//memset(edge,0,sizeof(edge));
num=-1;
s=0;t=x*n*m+n*m+1;
for(re int i=1;i<=n;i++)
for(re int j=1;j<=m;j++){
if(map[i][j]=='.') add(s,id,1);
if(map[i][j]=='D'){
add(n*m+id,t,1);
for(re int l=2;l<=x;l++)
{
add((l-1)*n*m+id,l*n*m+id,inf);
add(l*n*m+id,t,1);
}
for(re int p=1;p<=n;p++)
for(re int q=1;q<=m;q++)
if(map[p][q]=='.'&&dis[idd[p][q]][idd[i][j]]<100000)
add(idd[p][q],dis[idd[p][q]][idd[i][j]]*n*m+id,1);
}
}
return dinic()==tot;
}
int main()
{
n=read();m=read();
for(re int i=1;i<=n;i++)
for(re int j=1;j<=m;j++){
cin>>map[i][j];idd[i][j]=id;
for(re int p=1;p<=n;p++)
for(re int q=1;q<=m;q++)
dis[idd[i][j]][(p-1)*m+q]=dis[(p-1)*m+q][idd[i][j]]=inf;
}
for(re int i=1;i<=n*m;i++)
dis[i][i]=0;
for(re int i=1;i<=n;i++)
for(re int j=1;j<=m;j++)
{
if(map[i][j]=='.'){
tot++;
for(re int k=1;k<=4;k++)
{
int tx=i+dx[k],ty=j+dy[k];
if(map[tx][ty]!='X'&&tx>=1&&tx<=n&&ty>=1&&ty<=m){
dis[idd[i][j]][idd[tx][ty]]=1;
}
}
}
if(map[i][j]=='D')
{
for(re int k=1;k<=4;k++)
{
int tx=i+dx[k],ty=j+dy[k];
if(map[tx][ty]!='X'&&tx>=1&&tx<=n&&ty>=1&&ty<=m){
dis[idd[i][j]][idd[tx][ty]]=1;
}
}
}
}
for(re int k=1;k<=n*m;k++)
for(re int i=1;i<n*m;i++)
for(re int j=i+1;j<=n*m;j++)
if(i!=j&&j!=k&&k!=i)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
s=0;
int l=1,r=201;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
if(l>199)
cout<<"impossible";
else
cout<<l;
}
/*
3 3
XXX
X.X
XDX
*/