【HNOI2013】切糕

【HNOI2013】切糕

Sample Input

2 2 2
1
6 1
6 1
2 6
2 6

Sample Output

6

(P,Q,R≤40，0≤D≤R)

参考：https://blog.csdn.net/zarxdy34/article/details/45272055

经典的有距离限制的网络流模型。

首先我们不考虑高度限制。我们直接将图建(r+1)层，就是每个格子((x,y))拆成(r+1)个点。将它们串成一串，第(i)层的向(i+1)层连边，第(i)条边的容量就是(v_{x,y,i})。然后源点向第(1)层的连边，第(r+1)层的向汇点连边。最小割就是答案。

考虑怎么将距离限制表示出来。对于所有的格子((x,y))，假设是第(k)层的图，那么我们向第(k-d)层的((x,y))周围的点连(infty)的边。

考虑这么做的合法性。两个相邻的格子((x,y),(x',y'))，如果我们选了(v_{x,y,k})，也就是割断了第(k)层((x,y))连出去的边，那么((x',y'))选的高度(k')要(geq k-D)。如果((x',y'))割断了(k-D)以下的边，那么((x,y))和((x',y'))之间(infty)的边就会实源点和汇点连通。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 45

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const int V=N*N*N;
int n,m,r;
int D;
int v[N][N][N];
int id[N][N];
struct road {
	int to,next;
	int flow;
}s[V<<3];
int h[V],cnt=1;
void add(int i,int j,int f) {
	s[++cnt]=(road) {j,h[i],f};h[i]=cnt;
	s[++cnt]=(road) {i,h[j],0};h[j]=cnt;
}
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};

int S,T;
int dis[V];
queue<int>q;
bool bfs() {
	memset(dis,0x3f,sizeof(dis));
	q.push(S);
	dis[S]=0;
	while(!q.empty()) {
		int v=q.front();
		q.pop();
		for(int i=h[v];i;i=s[i].next) {
			int to=s[i].to;
			if(s[i].flow&&dis[to]>dis[v]+1) {
				dis[to]=dis[v]+1;
				q.push(to);
			}
		}
	}
	return dis[T]<1e9;
}

int dfs(int v,int maxf) {
	if(v==T) return maxf;
	int ret=0;
	for(int i=h[v];i;i=s[i].next) {
		int to=s[i].to;
		if(s[i].flow&&dis[to]==dis[v]+1) {
			int dlt=dfs(to,min(maxf,s[i].flow));
			s[i].flow-=dlt;
			s[i^1].flow+=dlt;
			ret+=dlt;
			maxf-=dlt;
			if(!maxf) return ret;
		}
	}
	return ret;
}

int dinic() {
	int ans=0;
	while(bfs()) {
		while(1) {
			int tem=dfs(S,1e9);
			if(!tem) break;
			ans+=tem;
		}
	}
	return ans;
}

int main() {
	n=Get(),m=Get(),r=Get();
	D=Get();
	for(int k=1;k<=r;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				v[i][j][k]=Get();
	int tot=n*m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			id[i][j]=(i-1)*m+j;
	T=(r+1)*tot+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			add(S,id[i][j],1e9),add(id[i][j]+r*tot,T,1e9);
	
	for(int k=1;k<=r;k++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				add((k-1)*tot+id[i][j],k*tot+id[i][j],v[i][j][k]);
				if(k>D) {
					int nxt=k-D;
					for(int d=0;d<4;d++) {
						int a=i+dx[d],b=j+dy[d];
						if(a<1||a>n||b<1||b>m) continue ;
						add((k-1)*tot+id[i][j],(nxt-1)*tot+id[a][b],1e9);
					}
				}
			}
		}
	}
	cout<<dinic();
	return 0;
}