题解 P3851 【[TJOI2007]脱险】

· · 题解

分层图最大流

建议和[CTSC1999]家园一起做，因为这两道题的思路基本上是一样的。

按照时间建T+1层分层图，每一层都是n*m个点对应着这个时刻原图的n*m个点。

首先源点向第0层的每个探险队员点连流量为1的边，如果最终能流到了汇点说明这个人逃脱了。

对于任意一层：

(首先规定障碍永不连边)

每个位置在这一层对应点向每个他能到达的位置(上下左右)在下一层对应点连一条流量为inf的边，表示这一秒可以有任意多的人从一个空地移动到另一块空地。

每个空地/出口在这一层的对应点向它在下一层的对应点连inf的边表示这个位置可以容纳inf个人不动。

每个出口在这一层的对应点向汇点连一条流量为1的边表示每个时刻只允许一个人脱险。

然后直接跑dinic求最大流即为答案

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
#define mp(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    int ans=0,fh=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        ans=ans*10+ch-'0',ch=getchar();
    return ans*fh;
}
const int maxn=1e4+100,maxm=5e5+100,maxd=20;
const int inf=0x7fffffff;
int n,m,T,head[maxn],nex[maxm],v[maxm],w[maxm],num=1;
int p[maxd][maxd],bh[maxd][maxd],cur[maxn],cc[maxn],s,t;
int uu[4]={1,0,-1,0},vv[4]={0,-1,0,1};
char c[maxd];
queue<int>q;
inline void add(int x,int y,int z){
    v[++num]=y,w[num]=z,nex[num]=head[x],head[x]=num;
    v[++num]=x,w[num]=0,nex[num]=head[y],head[y]=num;
}
inline void build(){
    s=0,t=maxn-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(p[i][j]==2) add(s,bh[i][j],1);
    int nm=n*m;
    for(int d=0;d<=T;d++){
        int st=nm*d;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(!p[i][j]) continue;
                int x=st+bh[i][j];
                for(int k=0;k<4;k++){
                    int vx=i+uu[k],vy=j+vv[k];
                    if(vx<1||vx>n||vy<1||vy>m) continue;
                    if(p[vx][vy]) add(x,st+nm+bh[vx][vy],inf);
                }
                if(p[i][j]==3) add(x,t,1),add(x,x+nm,1);
                else add(x,x+nm,inf);
            }
    }
}
inline bool bfs(){
    memset(cc,0,sizeof(cc));
    cc[s]=1,q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nex[i]){
            int y=v[i];if(!w[i]) continue;
            if(!cc[y]) cc[y]=cc[x]+1,q.push(y);
        }
    }
    return cc[t];
}
int dfs(int x,int lv){
    if(x==t) return lv;
    for(int &i=cur[x];i;i=nex[i]){
        int y=v[i];if(!w[i]) continue;
        if(cc[y]==cc[x]+1){
            int pp=dfs(y,lv>w[i]?w[i]:lv);
            if(pp){
                w[i]-=pp,w[i^1]+=pp;
                return pp;
            }
        }
    }
    return 0;
}
inline int dinic(){
    int maxl=0,lv=0;
    while(bfs()){
        memcpy(cur,head,sizeof(cur));
        while(lv=dfs(s,inf)) maxl+=lv;
    }
    return maxl;
}
int main(){
//  freopen("nh.in","r",stdin);
//  freopen("zhy.out","w",stdout);
    n=read(),m=read(),T=read();
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        for(int j=1;j<=m;j++){
            bh[i][j]=(i-1)*m+j;
            if(c[j]=='.') p[i][j]=1;
            if(c[j]=='P') p[i][j]=2;
            if(c[j]=='O') p[i][j]=3;
        }
    }
    build();
    printf("%d\n",dinic());
    return 0;
}