P3191 [HNOI2007]紧急疏散EVACUATE（费用流）

P3191 [HNOI2007]紧急疏散EVACUATE

费用流+卡常优化

我们只关心一个人通过门时的时间，在空地的行走时间可以分层维护

于是根据时间分层，到门的时候再计算代价，即代价$=$层数

每经过$1$单位时间就向下走一层

然后就是优化：

1. 删去多余点（层）：只要开和人数相同的层，因为一个人的等待时间一定小等于人数

2. 能预处理的尽量预处理

3. register，快读，inline等

4. 能不用stl尽量不用（使用stl:queue=TLE），建议手写队列

复杂度$O($卡常能过$)$，详情可看code

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
using namespace std;
#define N 200005
#define M 3000005
const int d1[4]={0,1,0,-1};
const int d2[4]={1,0,-1,0};
char a[30][30];
int n,m,nm,mx,ans,tot,S,T,v[N],p[N],id[30][30];
bool vis[N]; int h[M],L,R;
int Cnt=1,hd[N],nxt[M],ed[N],poi[M],con[M],val[M];
void adde(int x,int y,int v1,int v2){
    nxt[ed[x]]=++Cnt; hd[x]=hd[x]?hd[x]:Cnt;
    ed[x]=Cnt; poi[Cnt]=y; con[Cnt]=v1; val[Cnt]=v2;
}
inline void link(int x,int y,int v1,int v2){adde(x,y,v1,v2),adde(y,x,0,-v2);}
#define to poi[i]
bool bfs(){//普通费用流
    memset(v,63,sizeof(v)); int inf=v[0];
    h[L=1]=S; R=2; vis[S]=1; v[S]=0;
    while(L!=R){
        re int x=h[L++]; vis[x]=0;
        if(L>=M) L=1;
        for(re int i=hd[x];i;i=nxt[i])
            if(con[i]&&v[to]>v[x]+val[i]){
                v[to]=v[x]+val[i]; p[to]=i;
                if(!vis[to]){
                    vis[to]=1,h[R++]=to;
                    if(R>=M) R=1;
                }
            }
    }if(v[T]==inf) return 0;
    tot-=1; ans=max(ans,v[T]);
    for(re int u=T;u!=S;u=poi[p[u]^1])
        con[p[u]]-=1,con[p[u]^1]+=1;
    return 1;
}//因为每次流量均为1，可以省去流量数组
void draw(int x,int y){
    re int p=id[x][y];
    if(a[x][y]=='X') return ;
    if(a[x][y]=='D') for(re int i=1;i<=mx;++i) link(p+i*nm,T,1,i);//分层与终点连边，代价=层数
    if(a[x][y]=='.'){
        link(S,p,1,0); ++tot;
        for(re int i=0;i<mx;++i){
            link(p+i*nm,p+(i+1)*nm,1e9,0);
            for(re int j=0;j<4;++j){
                int rx=x+d1[j],ry=y+d2[j];
                if(a[rx][ry]=='X') continue;
                link(p+i*nm,id[rx][ry]+(i+1)*nm,1e9,0);//与四周连边
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);  S=N-4; T=N-3; nm=n*m;
    for(re int i=1;i<=n;++i) scanf("%s",a[i]+1);
    for(re int i=1;i<=n;++i)
        for(re int j=1;j<=m;++j)
            mx+=(a[i][j]=='.'),id[i][j]=(i-1)*m+j;//mx：人数，建图需要的层数
    for(re int i=1;i<=n;++i) for(re int j=1;j<=m;++j) draw(i,j);
    while(bfs()) ;
    if(tot) puts("impossible");
    else printf("%d",ans);
    return 0;
}

P3191 [HNOI2007]紧急疏散EVACUATE（费用流）

推荐阅读