P3191 [HNOI2007] 紧急疏散EVACUATE

· · 题解

套路题，给个不用二分的写法。

一眼网络流。

将人看做流量。每个格子拆成两个点，从入点连向出点，如果是门那么容量是 1，否则是 +\infin。含义是这个位置能站几个人。

涉及到时间所以建分层图。现在在 (x, y)，那么从上一层的 (x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1), (x, y) 的出点连边到这一层 (x, y) 的入点，容量 +\infin。表示人能从别的格子花费 1 时间到达这里。注意上一层必须是空地才能连边过来。

对于第一层，源点向每个空地连边，容量为 1，表示最开始这里有一个人。

对于每一层，门位置的出点（入点也行）连向汇点，容量为 1，表示每个时间只能一个人逃出去。

但是因为时间不知道，所以不知道要建多少层。所以直接一层一层加上去，然后加上新增的流量，直到第一次总流量等于人数，此时的层数减去一就是答案。

注意判断无解的情况。因为 nm \leq 400 所以如果建了 400 层流量仍然小于人数，说明无解。

#include<queue>
#include<cstdio>
#include<cstring>
const int M=5e5+10;
const int inf=1e9+7;
const int dx[]={-1,1,0,0},
          dy[]={0,0,-1,1};

int n,m;
char mp[23][23];

int head[M],cnte=1;
struct Edge{
    int to,nxt,cap,flow;
}e[M<<2];
void add(int u,int v,int w){
    e[++cnte]={v,head[u],w,0};
    head[u]=cnte;
}
void Add(int u,int v,int w){
    add(u,v,w),add(v,u,0);
}

std::queue<int>q;
int dis[M],s,t,cntp;
bool bfs(){
    for(int i=0;i<=cntp;i++) dis[i]=0;
    dis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].cap>e[i].flow&&!dis[v]){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[t];
}
int dfs(int u,int in){
    if(u==t) return in;
    int out=0;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].cap>e[i].flow){
            int res=dfs(v,std::min(in,e[i].cap-e[i].flow));
            e[i].flow+=res,e[i^1].flow-=res;
            in-=res,out+=res;
        }
    }
    if(!out) dis[u]=-1;
    return out;
}
int Dinic(){
    int ans=0;
    while(bfs()) ans+=dfs(s,inf);
    return ans;
}

int iD[2][23][23][2],cur;
void BasicLayer(){
    cur^=1;
    s=0,t=cntp=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='X') continue;
            iD[1][i][j][0]=++cntp;
            iD[1][i][j][1]=++cntp;
            if(mp[i][j]=='.'){
                Add(iD[1][i][j][0],iD[1][i][j][1],1);
                Add(s,iD[1][i][j][0],1);
            }
            if(mp[i][j]=='D'){
                Add(iD[1][i][j][0],iD[1][i][j][1],1);
                Add(iD[1][i][j][1],t,1);
            }
        }

}
void NewLayer(){
    cur^=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='X') continue;
            iD[cur][i][j][0]=++cntp;
            iD[cur][i][j][1]=++cntp;
            Add(iD[cur^1][i][j][1],iD[cur][i][j][0],inf);
            for(int dir=0;dir<4;dir++){
                int x=i+dx[dir],y=j+dy[dir];
                if(x<1||x>n||y<1||y>m) continue;
                if(mp[x][y]!='.') continue;
                Add(iD[cur^1][x][y][1],iD[cur][i][j][0],inf);
            }
            if(mp[i][j]=='.'){
                Add(iD[cur][i][j][0],iD[cur][i][j][1],inf);
            }
            if(mp[i][j]=='D'){
                Add(iD[cur][i][j][0],t,1);
            }
        }
}

int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf(" %s",mp[i]+1);
    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cnt+=(mp[i][j]=='.');

    BasicLayer();
    int all=0;
    for(int t=1;;t++){
        if(t>=400) break;
        NewLayer();
        all+=Dinic();
        if(all==cnt){
            printf("%d\n",t);
            return 0;
        }
    }
    printf("impossible\n");
    return 0;
}