洛谷3191 [HNOI2007]紧急疏散EVACUATE

Luogu

BZOJ

分析

二分答案、bfs、最大流。

首先二分时间$mid$。

对于每个空地$(i,j)$,从源点向$(i,j)$连一条容量为$1$的边。

把每扇门拆成$mid$个点$(i,t)$,表示第$i$扇门在时刻$t$。所有拆出来的点都向汇点连容量为$1$的边。

如果一个人能在$t$时刻到达第$i$扇门,则向$(i,t)$连容量为$1$的边。

但是这样子总连边量很大,每个人向每扇门可以只连那个最小的$t$,然后每个$(i,t)$向$(i,t+1)$连容量为$\infty$的边。可以发现这样是等效的。

如何算出这个最小的$t$,直接对每扇门$\mathrm{bfs}$,求出最短路就行呀。

然后,请做好DEBUG半天的准备。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20+10;
const int INF=2e9;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};

struct Edge { int v,w,nxt; };
Edge e[1000000];
int head[100000],cnt=0;

inline void clearGraph() { memset(head,-1,sizeof(head)); cnt=0; }
inline void addEdge(int u,int v,int w) {
    e[cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt++;
    e[cnt].v=u,e[cnt].w=0,e[cnt].nxt=head[v],head[v]=cnt++;
}

int n,m;
char str[N][N];
int door_tot=0,empty_tot=0;
int g[N][N];
int vis[N][N],dis[N*N][N][N];

namespace Init {
    struct Point { int x,y; };
    inline void bfs(int id,int sx,int sy) {
        memset(vis,0,sizeof(vis));
        dis[id][sx][sy]=0,vis[sx][sy]=1;
        queue<Point> Q; Q.push((Point){sx, sy});
        while (!Q.empty()) {
            Point fr=Q.front(); Q.pop();
            int x=fr.x,y=fr.y;
            for (re int i=0;i<4;++i) {
                int X=x+dx[i],Y=y+dy[i];
                if (X<1||X>n||Y<1||Y>m||vis[X][Y]||str[X][Y]!='.') continue;
                dis[id][X][Y]=dis[id][x][y]+1,vis[X][Y]=1;
                Q.push((Point){X,Y});
            }
        }
    }
    inline void work() {
        memset(dis,0x3f,sizeof(dis));
        n=read(),m=read();
        for (re int i=1;i<=n;++i) scanf("%s",str[i]+1);
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j) {
                if (str[i][j]=='D') bfs(++door_tot,i,j);
                else if (str[i][j]=='.') g[i][j]=++empty_tot;
            }
    }
}

namespace Dinic {
    int s,t;
    int level[100000];

    inline int bfs() {
        memset(level,0,sizeof(level));
        queue<int> Q; Q.push(s); level[s]=1;
        while (!Q.empty()) {
            int u=Q.front(); Q.pop();
            for (re int i=head[u];i!=-1;i=e[i].nxt) {
                int v=e[i].v;
                if (e[i].w&&!level[v])
                    level[v]=level[u]+1,Q.push(v);
            }
        }
        return level[t]!=0;
    }

    inline int dfs(int u,int cpflow) {
        if (u==t) return cpflow;
        int addflow=0;
        for (re int i=head[u];i!=-1;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&level[v]==level[u]+1) {
                int tmpadd=dfs(v,min(cpflow-addflow,e[i].w));
                e[i].w-=tmpadd,e[i^1].w+=tmpadd;
                addflow+=tmpadd;
            }
        }
        if (!addflow) level[u]=0;
        return addflow;
    }

    inline int work(int x,int y) {
        int maxflow=0; s=x,t=y; 
        while (bfs()) maxflow+=dfs(x,INF);
        return maxflow;
    }
}

namespace Main {
    inline int check(int mid) {
        int s=0,t=door_tot*mid+empty_tot+1;
        clearGraph();
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j)
                if (str[i][j]=='.') addEdge(s,g[i][j],1);
        for (re int i=1;i<=door_tot;++i) {
            int tmp=(i-1)*mid+empty_tot;
            for (re int j=1;j<mid;++j) {
                addEdge(tmp+j,t,1);
                addEdge(tmp+j,tmp+j+1,INF);
            }
            addEdge(tmp+mid,t,1);
        }
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=m;++j)
                for (re int k=1;k<=door_tot;++k)
                    if (str[i][j]=='.'&&dis[k][i][j]<=mid)
                        addEdge(g[i][j],(k-1)*mid+empty_tot+dis[k][i][j],1);
        return Dinic::work(s,t)==empty_tot;
    }
    inline void work() {
        int L=1,R=1e3,ans=-1;
        while (L<=R) {
            int mid=(L+R)>>1;
            if (check(mid)) ans=mid,R=mid-1;
            else L=mid+1;
        }
        if (ans==-1) puts("impossible");
        else printf("%d\n",ans);
    }
}

int main() {
    Init::work();
    Main::work();
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 04 PM

4 条评论

  1. xgzc

    请做好写半天的准备QAQ

    1. M_sea
      @xgzc

      您不是随便就切了吗qwq

  2. smy

    debug半天是smg

    1. M_sea
      @smy

      我的话至少要debug半天,您的话写完直接交就可以AC

发表评论