P3191 [HNOI2007]紧急疏散EVACUATE

传送门

这一题很容易想到网络流

一开始傻逼地模拟整个图每一个时间的情况，显然会爆炸

发现我们只要考虑起点到门之间的距离，不用每一步只走一格

所以直接 $BFS$ 预处理距离然后二分答案，网络流判断即可

注意到了门就不能走了，所以门不能连边出去

总的来说挺傻逼的一题...但是我就是没想到...

某位不愿意透露姓名的神仙还有一种牛逼的费用流做法，代码极短$STO$

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+,M=5e6+,INF=1e9+,xx[]={,,,-},yy[]={,,-,};

int fir[N],from[M<<],to[M<<],val[M<<],cntt=;

inline void add(int a,int b,int c)

{

    from[++cntt]=fir[a]; fir[a]=cntt;

    to[cntt]=b; val[cntt]=c;

    from[++cntt]=fir[b]; fir[b]=cntt;

    to[cntt]=a; val[cntt]=;

}

int n,m,tot,id[][][],sum;

int dep[N],S,T;

queue <int> Q;

bool BFS()

{

    for(int i=;i<=tot;i++) dep[i]=;

    Q.push(S); dep[S]=;

    while(!Q.empty())

    {

        int x=Q.front(); Q.pop();

        for(int i=fir[x];i;i=from[i])

        {

            int &v=to[i]; if(dep[v]||(!val[i])) continue;

            dep[v]=dep[x]+; Q.push(v);

        }

    }

    return dep[T]>;

}

int DFS(int x,int mxfl)

{

    if(x==T||!mxfl) return mxfl;

    int fl=,res;

    for(int i=fir[x];i;i=from[i])

    {

        int &v=to[i]; if(dep[v]!=dep[x]+||!val[i]) continue;

        if( res=DFS(v,min(mxfl,val[i])) )

        {

            mxfl-=res; fl+=res;

            val[i]-=res; val[i^]+=res;

            if(!mxfl) break;

        }

    }

    return fl;

}

char mp[][];

int dis[][][][];

struct dat{

    int x,y;

    dat (int a=,int b=) { x=a,y=b; }

};

queue <dat> q;

void pre()

{

    memset(dis,0x3f,sizeof(dis));

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            if(mp[i][j]!='.') continue;

            q.push(dat(i,j)); dis[i][j][i][j]=;

            while(!q.empty())

            {

                dat u=q.front(); q.pop();

                for(int k=;k<;k++)

                {

                    int tx=u.x+xx[k],ty=u.y+yy[k];

                    if(tx<||tx>n||ty<||ty>m||mp[tx][ty]=='X'||dis[i][j][tx][ty]<M) continue;

                    dis[i][j][tx][ty]=dis[i][j][u.x][u.y]+;

                    if(mp[tx][ty]!='D') q.push(dat(tx,ty));

                }

            }

        }

}

bool check(int mid)

{

    for(int i=;i<=tot;i++) fir[i]=; tot=; S=,T=; cntt=;

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            if(mp[i][j]=='.') id[][i][j]=++tot,add(S,tot,);

    for(int t=;t<=mid;t++)

        for(int k=;k<=n;k++)

            for(int l=;l<=m;l++)

                if(mp[k][l]=='D') id[t][k][l]=++tot,add(tot,T,);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            if(mp[i][j]!='.') continue;

            for(int t=;t<=mid;t++)

                for(int k=;k<=n;k++)

                    for(int l=;l<=m;l++)

                        if(mp[k][l]=='D'&&dis[i][j][k][l]<=t) add(id[][i][j],id[t][k][l],INF);

        }

    int now=;

    while(BFS())

    {

        now+=DFS(S,INF);

        if(now>=sum) break;

    }

    for(int t=;t<=mid;t++)

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++) id[t][i][j]=;

    return now>=sum;

}

int main()

{

    n=read(),m=read();

    for(int i=;i<=n;i++) scanf("%s",mp[i]+);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) sum+=(mp[i][j]=='.');

    pre();

    int L=,R=n*m,mid,ans=M;

    while(L<=R)

    {

        mid=L+R>>;

        if(check(mid)) R=mid-,ans=mid;

        else L=mid+;

    }

    if(ans==M) printf("impossible\n");

    else printf("%d\n",ans);

    return ;

}