自动搬运

查看原文

来自洛谷，原作者为

	nianheng ?!

搬运于2025-08-24 21:53:23，当前版本为作者最后更新于2019-06-18 10:49:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分层图最大流

建议和[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;
}