「BZOJ3144」[HNOI2013]切糕

Description

经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B 。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮她找出最好的切割方案。
出于简便考虑,我们将切糕视作一个长 PP 、宽 QQ 、高 RR 的长方体点阵。我们将位于第 zz 层中第 xx 行、第 yy 列上 (1xP,1yQ,1zR)(1 \le x \le P, 1 \le y \le Q, 1 \le z \le R) 的点称为 (x,y,z)(x,y,z) ,它有一个非负的不和谐值 v(x,y,z)v(x,y,z) 。一个合法的切面满足以下两个条件:

  • 与每个纵轴(一共有 P×QP\times Q 个纵轴)有且仅有一个交点。即切面是一个函数 f(x,y)f(x,y) ,对于所有 1xP,1yQ1 \le x \le P, 1 \le y \le Q ,我们需指定一个切割点 f(x,y)f(x,y) ,且 1f(x,y)R1 \le f(x,y) \le R
  • 切面需要满足一定的光滑性要求,即相邻纵轴上的切割点不能相距太远。对于所有的 1x,xP1 \le x,x’ \le P1y,yQ1 \le y,y’ \le Q ,若 xx+yy=1|x-x’|+|y-y’|=1 ,则 f(x,y)f(x,y)D|f(x,y)-f(x’,y’)| \le D ,其中 DD 是给定的一个非负整数。
    可能有许多切面 ff 满足上面的条件,小 A 希望找出总的切割点上的不和谐值最小的那个,即 x,yv(x,y,f(x,y))\sum_{x,y}{v(x, y, f (x, y))} 最小。

Input

输入文件第一行是三个正整数 PP , QQ , RR ,表示切糕的长 PP 、宽 QQ 、高 RR
第二行有一个非负整数 DD ,表示光滑性要求。
接下来是 RRPPQQ 列的矩阵,第 zz 个矩阵的第 xx 行第 yy 列是 v(x,y,z)(1xP,1yQ,1zR)v(x,y,z) (1 \le x \le P, 1 \le y \le Q, 1 \le z \le R)

Output

输出仅包含一个整数,表示在合法基础上最小的总不和谐值。

Sample Input

1
2
3
4
5
6
2 2 2
1
6 1
6 1
2 6
2 6

Sample Output

1
6

HINT

对于 100%100\% 的数据, P,Q,R40,0DRP,Q,R \le 40 , 0 \le D \le R ,且给出的所有的不和谐值不超过 10001000

Solution

考虑没有DD的限制:

  • (i,j,k)(i,j,k)(i+1,j,k)(i+1,j,k)连容量为ai,j,ka_{i,j,k}的边
  • ss(1,j,k)(1,j,k)连容量为infinf的边
  • (r+1,j,k)(r+1,j,k)tt连容量为infinf的边。

跑一个最大流即为答案。
那么有DD的限制该怎么办?每一个(i,j,k)(i,j,k)(i,j,kD)(i',j',k-D)连容量为infinf的边。
why?

看图,如果限制D=2D=2,假如考虑33这个点。

搞一搞,发现如果(3,4)(3,4)是割边的话,那么(s,5)(s,5)一定不是。也就是满足titjDt_i-t_j\leq Dtt表示相对编号。
如果各自连的话就是titjDt_i-t_j\leq DtjtiDt_j-t_i\leq 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
103
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 50*50*45, M = 50 * 50 * 50*3;
int p, q, r;
int D;
int id(int x, int y, int z) {
return (z - 1) * p * q + (x - 1) * q + y;
}
int a[51][51][51];
struct Edge {
int u, v, nxt, f;
}e[M*2];
int head[N], en = 1;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt =head[x], head[x] = en,e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
const int inf = 1e9;
int s, t;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int d[N];
bool bfs() {
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
queue<int>q;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f) {
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f && d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(rest, e[i].f));
rest -= k;
e[i ^ 1].f += k;
e[i].f -= k;
}
if(flow - rest == 0) d[x] = 0;
return flow - rest;
}
int main() {
p = read(), q = read(), r = read();
D = read();
for(int i = 1; i <= r; ++i)
for(int j = 1; j <= p; ++j)
for(int k = 1; k <= q; ++k)
a[i][j][k] = read();
s = (r + 1) * p * q + 1;
t = (r + 1) * p * q + 2;
for(int i = 1; i <= p; ++i)
for(int j = 1; j <= q; ++j) {
addedge(s, (i - 1) * q + j, inf);
addedge(id(i, j, r + 1), t, inf);
}
for(int i = 1; i <= r; ++i)
for(int j = 1; j <= p; ++j)
for(int k = 1; k <= q; ++k) {
addedge(id(j, k, i), id(j, k, i + 1), a[i][j][k]);
if(i > D ) {
for(int t = 0; t < 4; ++t) {
int nx = j + dx[t];
int ny = k + dy[t];
if(nx < 1 || nx > p || ny < 1 || ny > q) continue;
addedge(id(j, k, i), id(nx, ny, i - D), inf);
}
}
}
int res = 0, y;
while(bfs()) while(y = dinic(s, inf)) res += y;

writeln(res);
return 0;
}