切糕

发表于 | 分类于

题目

传送门
经过千辛万苦小A 得到了一块切糕，切糕的形状是长方体，小A 打算拦腰将切糕切成两半分给小B。出于美观考虑，小A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。

出于简便考虑，我们将切糕视作一个长P、宽Q、高R 的长方体点阵。我们将位于第z层中第x 行、第y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z)，它有一个非负的不和谐值v(x,y,z)。一个合法的切面满足以下两个条件：

  1. 与每个纵轴(一共有P×Q 个纵轴)有且仅有一个交点。即切面是一个函数f(x,y)，对于所有1≤x≤P, 1≤y≤Q,我们需指定一个切割点f(x,y),且1≤f(x,y)≤R。
  2. 切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的1≤x,x’≤P 和1≤y,y’ ≤Q，若|x-x’|+|y-y’|=1，则|f(x,y)-f(x’,y’)| ≤D，其中D 是给定的一个非负整数。

可能有许多切面f 满足上面的条件，小A 希望找出总的切割点上的不和谐值最小的那个，即v(x, y, f (x, y))x,y最小。

INPUT

从文件input.txt中读入数据，输入文件第一行是三个正整数P,Q,R，表示切糕的长P、宽Q、高R。第二行有一个非负整数D，表示光滑性要求。接下来是R个P行Q列的矩阵，第z个矩阵的第x行第y列是v(x,y,z) (1≤x≤P,1≤y≤Q, 1≤z≤R)。
100%的数据满足P,Q,R≤40，0≤D≤R，且给出的所有的不和谐值不超过1000。

OUTPUT

输出文件output.txt 仅包含一个整数，表示在合法基础上最小的总不和谐值。

SAMPLE

INPUT1

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

OUTPUT1

6

INPUT2

2 2 2
0
5 1
5 1
2 5
2 5

OUTPUT2

12

EXPLAIN

第一组样例中最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1。
第二组样例中最佳切面的f为f(1,1)=f(2,1)=f(1,2)=f(2,2)=1。

解题报告

极其 （！@#） 的一道题，反正我在建边时蒙成了 （！@#）。
由题意得知，显然为最小割模型，将点权转化为边权。由S向(x,y,1)连边，边权为v(x, y,1)。由(x, y, z)向(x, y, z+1)连边，边权为v(x, y, z+1)。
最后由(x, y, R)向T连边，边权为INF。此题关键为这个选择的距离限制。
我们可以这样解决：由每个点向它相邻的点的下方的第d个点连边。也就由(x, y, z)向(x, y, z-d)连边，边权为INF。
首先，假设每条纵轴只割一条边。若两条边的距离大于d，一定会有图中所示路径，此时仍需要再割一条边。
假设再割一条右侧的边，此边与左边割掉的那条边的距离要 ≤ d，否则还会出现这样的路径。
只有距离 ≤ d，才能截断。
但此时，右边第一次截断的边已经没有必要了。因为只要上面两条边就可以截断了。
因此，每个纵轴只截断一条边，且相邻截断的边距离一定 ≤ d。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[1000001];
int pre[64500],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int p,q,r,d;
int id[41][41][41],w[41][41][41];
int cnt(0);
int S(0),T;
int ans(0),inf(0x7fffffff);
int dis[64500];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
}
inline int gg(){
	freopen("nutcake.in","r",stdin);
	freopen("nutcake.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	p=read(),q=read(),r=read(),d=read();
	T=p*q*r+1;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=p;j++)
			for(int k=1;k<=q;k++){
				w[i][j][k]=read();
				id[i][j][k]=++cnt;
				insert(id[i-1][j][k],id[i][j][k],w[i][j][k]),insert(id[i][j][k],id[i-1][j][k],0);
				if(i==r)
					insert(id[i][j][k],T,inf),insert(T,id[i][j][k],0);
				if(i>d){
					if(j!=1)
						insert(id[i][j][k],id[i-d][j-1][k],inf),insert(id[i-d][j-1][k],id[i][j][k],0);
					if(j!=p)
						insert(id[i][j][k],id[i-d][j+1][k],inf),insert(id[i-d][j+1][k],id[i][j][k],0);
					if(k!=1)
						insert(id[i][j][k],id[i-d][j][k-1],inf),insert(id[i-d][j][k-1],id[i][j][k],0);
					if(k!=q)
						insert(id[i][j][k],id[i-d][j][k+1],inf),insert(id[i-d][j][k+1],id[i][j][k],0);
				}
			}
	while(bfs(S,T))
		ans+=dfs(S,inf);
	printf("%d",ans);
	return 0;
}
int K(gg());
int main(){;}