@description@
一个长 P 宽 Q 高 R 的长方体点阵，每个点 (x, y, z) 有一个权值 v(x, y, z)。
请找到一个函数 f(x, y) 使得 1 ≤ f(x, y) ≤ R 且对于 |x - x'| + |y - y'| = 1，必须有 |f(x, y) - f(x', y')| ≤ D。
最小化 ∑v(x, y, f(x, y))。
Input
第一行是三个正整数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
仅包含一个整数，表示在合法基础上最小的总不和谐值。
Sample Input
2 2 2
1
6 1
6 1
2 6
2 6
Sample Output
6
@solution@
经典中的经典.jpg。
考虑 |f(x, y) - f(x', y')| ≤ D 可以拆成 f(x, y) ≤ f(x', y') + D 与 f(x', y') ≤ f(x, y) + D。
于是我们只需要保证一对 (x, y) 相邻的 f 值 ≤ 它本身的 f 值 + D 即可。
考虑上式，其实相当于规定一些点不能够共存，这使我们联想到最小割。
我们对于每一对 (x, y) 建 R 个点串成一条链，源点连链头，汇点连链尾。在这条链上割掉 (a, b) 这条边相当于令 f(x, y) = b（a 可以为源点），所以我们令 (a, b) 的容量为 v(x, y, b)，当 b 为汇点时容量为 inf。
考虑怎么用 inf 边表示我们的矛盾与共存关系。
依上所述，假如 (x', y') 与 (x, y) 相邻，对于 (x, y) 中的第 i 个点，我们可以从 (x', y') 中的第 i + D 个点出发连一条 inf 边向 (x, y) 中的第 i 个点。
这样的话，假如我们选中了第 i 个点（相当于割掉第 i 个点之前的边），则会出现路径 s -> (x', y') 的 i + D -> (x, y) 的 i -> t。
因为选中 “(x, y) 的 i -> t” 这一段路径割肯定会不优（每条路径只割一条边是最优的），所以我们必然会割 “s -> (x', y') 的 i + D” 这一段，而这就完成了我们的目的。
@accepted code@
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 45;
const int MAXV = MAXN*MAXN*MAXN;
const int MAXE = 30*MAXV;
const int INF = (1<<30);
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct FlowGraph{
struct edge{
int to, cap, flow;
edge *nxt, *rev;
}edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt;
FlowGraph() {ecnt = &edges[0];}
void addedge(int u, int v, int c) {
edge *p = (++ecnt), *q = (++ecnt);
p->to = v, p->cap = c, p->flow = 0;
p->nxt = adj[u], adj[u] = p;
q->to = u, q->cap = 0, q->flow = 0;
q->nxt = adj[v], adj[v] = q;
p->rev = q, q->rev = p;
}
int d[MAXV + 5], s, t;
queue<int>que;
bool relabel() {
for(int i=s;i<=t;i++)
d[i] = INF, cur[i] = adj[i];
d[t] = 0; que.push(t);
while( !que.empty() ) {
int f = que.front(); que.pop();
for(edge *p=adj[f];p;p=p->nxt)
if( p->rev->cap > p->rev->flow )
if( d[f] + 1 < d[p->to] ) {
d[p->to] = d[f] + 1;
que.push(p->to);
}
}
return !(d[s] == INF);
}
int aug(int x, int tot) {
if( x == t ) return tot;
int sum = 0;
for(edge *&p=cur[x];p;p=p->nxt) {
if( p->cap > p->flow && d[p->to] + 1 == d[x] ) {
int del = aug(p->to, min(tot - sum, p->cap - p->flow));
p->flow += del, p->rev->flow -= del, sum += del;
if( sum == tot ) return sum;
}
}
return sum;
}
int max_flow(int _s, int _t) {
s = _s, t = _t; int flow = 0;
while( relabel() )
flow += aug(s, INF);
return flow;
}
}G;
int P, Q, R, D, s, t;
int id[MAXN][MAXN][MAXN], cnt;
int v[MAXN][MAXN][MAXN];
int main() {
scanf("%d%d%d%d", &P, &Q, &R, &D);
for(int i=1;i<=R;i++)
for(int j=1;j<=P;j++)
for(int k=1;k<=Q;k++)
scanf("%d", &v[i][j][k]), id[i][j][k] = (++cnt);
s = 0, t = cnt + 1;
for(int i=1;i<=R;i++)
for(int j=1;j<=P;j++)
for(int k=1;k<=Q;k++)
G.addedge(id[i-1][j][k], id[i][j][k], v[i][j][k]);
for(int j=1;j<=P;j++)
for(int k=1;k<=Q;k++)
G.addedge(id[R][j][k], t, INF);
for(int i=1;i+D<=R;i++)
for(int j=1;j<=P;j++)
for(int k=1;k<=Q;k++)
for(int l=0;l<4;l++) {
int x = j + dx[l], y = k + dy[l];
if( x < 1 || y < 1 || x > P || y > Q ) continue;
G.addedge(id[i+D][x][y], id[i][j][k], INF);
}
printf("%d
", G.max_flow(s, t));
}
@details@
同理，假如每个点有若干个连续的状态 1...p[i]，某些点对之间会有限制（比如要求两个点选择的状态编号的差的绝对值不超过 k），则可以采用类似上文的建模方法。
据说这个模型叫作切糕模型。