切糕

切糕

首先，我们需要为每个点确定一个 \(1\) 到 \(k\) 的权值，这可以用以下的最小割模型描述：

接下来我们以 \(z=4\)，\(x' = x + 1\) 为例，找到描述第二个条件的方法。

先假设 \(S=0\)，考虑如何找到对应的连边方法。

我们以断 \((1,2)\) 为例，容易发现下面的构造：

接下来考虑 \(S=1\)，找到对应的连边。

你发现将所有边补充完整之后，这个图形如：

也就是说，我们会建立 \(O(nmk)\) 个点和 \(O(nmk)\) 条边，接下来跑最大流即可。

//Ad astra per aspera
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3f;
int n,s,t,from[648000],to[648000],nxt[648000],head[66666],edge_tot;
long long cap[648000];
void add_edge(int u,int v,long long w){
	from[edge_tot]=u;
	to[edge_tot]=v;
	cap[edge_tot]=w;
	nxt[edge_tot]=head[u];
	head[u]=edge_tot;
	edge_tot++;
}
void add(int u,int v,long long w){
	add_edge(u,v,w);
	add_edge(v,u,0); 
}
int cur[66666],level[66666];
bool bfs(){
	for(int i=1;i<=n;i++){
		level[i]=-1;
	}
	queue<int> q;
	level[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=nxt[i]){
			int v=to[i];
			if(cap[i]  &&  level[v]==-1){
				level[v]=level[u]+1;
				q.push(v);
			}
		}
	}
	return level[t]!=-1;
}
long long dfs(int u,long long flow){
	if(u==t  ||  flow==0){
		return flow;
	}
	long long ans=0;
	for(int i=cur[u];~i;i=nxt[i]){
		cur[u]=i;
		int v=to[i];
		if(cap[i]  &&  level[v]==level[u]+1){
			long long res=dfs(v,min(flow,cap[i]));
			ans+=res;
			flow-=res;
			cap[i]-=res;
			cap[i^1]+=res;
			if(flow==0){
				break;
			}
		}
	}
	return ans;
}
long long Dinic(){
	long long max_flow=0;
	while(bfs()){
		for(int i=1;i<=n;i++){
			cur[i]=head[i];
		}
		max_flow+=dfs(s,INF);
	}
	return max_flow;
}
long long W[50][50][50],new_id[50][50][50];
int main(){
	memset(head,-1,sizeof(head));
	memset(nxt,-1,sizeof(nxt));
	int N,M,K;
	scanf("%d %d %d",&N,&M,&K);
	int S;
	scanf("%d",&S);
	s=++n;
	t=++n;
	for(int z=1;z<=K;z++){
		for(int x=1;x<=N;x++){
			for(int y=1;y<=M;y++){
				scanf("%lld",&W[x][y][z]);
			}
		}
	}
	for(int x=1;x<=N;x++){
		for(int y=1;y<=M;y++){
			for(int z=0;z<=K;z++){
				new_id[x][y][z]=++n;
			}
			add(s,new_id[x][y][0],INF);
			add(new_id[x][y][K],t,INF);
			for(int z=1;z<=K;z++){
				add(new_id[x][y][z-1],new_id[x][y][z],W[x][y][z]);
			}
		}
	}
	for(int x=1;x<N;x++){
		for(int y=1;y<=M;y++){
			for(int i=S;i<=K;i++){
				add(new_id[x][y][i],new_id[x+1][y][i-S],INF);
				add(new_id[x+1][y][i],new_id[x][y][i-S],INF);
			}
		}
	}
	for(int x=1;x<=N;x++){
		for(int y=1;y<M;y++){
			for(int i=S;i<=K;i++){
				add(new_id[x][y][i],new_id[x][y+1][i-S],INF);
				add(new_id[x][y+1][i],new_id[x][y][i-S],INF);
			}
		}
	}
	printf("%lld",Dinic());
	return 0;
}