题目描述
经过千辛万苦小 A 得到了一块切糕，切糕的形状是长方体，小 A 打算拦腰将切糕切成两半分给小 B 。出于美观考虑，小 A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。
出于简便考虑，我们将切糕视作一个长 (P) 、宽 (Q) 、高 (R) 的长方体点阵。我们将位于第 (z) 层中第 (x) 行、第 (y) 列上 ((1 le x le P, 1 le y le Q, 1 le z le R)) 的点称为 ((x,y,z)) ，它有一个非负的不和谐值 (v(x,y,z)) 。一个合法的切面满足以下两个条件：
- 与每个纵轴(一共有 (P imes Q) 个纵轴)有且仅有一个交点。即切面是一个函数 (f(x,y)) ，对于所有 (1 le x le P, 1 le y le Q) ，我们需指定一个切割点 (f(x,y)) ，且 (1 le f(x,y) le R) 。
- 切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的 (1 le x,x’ le P) 和 (1 le y,y’ le Q) ，若 (|x-x’|+|y-y’|=1) ，则 (|f(x,y)-f(x’,y’)| le D) ，其中 (D) 是给定的一个非负整数。
可能有许多切面 (f) 满足上面的条件，小 A 希望找出总的切割点上的不和谐值最小的那个，即 (sum_{x,y}{v(x, y, f (x, y))}) 最小。
输入格式
输入文件第一行是三个正整数 (P) , (Q) , (R) ，表示切糕的长 (P) 、宽 (Q) 、高 (R) 。
第二行有一个非负整数 (D) ，表示光滑性要求。
接下来是 (R) 个 (P) 行 (Q) 列的矩阵，第 (z) 个矩阵的第 (x) 行第 (y) 列是 (v(x,y,z) (1 le x le P, 1 le y le Q, 1 le z le R)) 。
输出格式
输出仅包含一个整数，表示在合法基础上最小的总不和谐值。
题解
最小割 被CZH老师称作是模板题
首先看看第一个条件 对于每一个纵轴，我们都必须取一个高度(z)，表示这个纵轴从(z)这里切
我们可以这样来处理这件事情：
对于每条纵轴((x,y))，从源点连inf连向((x,y,1))，从((x,y,R+1))连inf连向汇点
然后对于每个(zin [1,R])，从((x,y,z))连一条流量为(v(x,y,z))的边连向((x,y,z+1))，像一条链一样
由于最后求的是最小割，所以这(R)条边里总是要割掉一条的，符合我们的题意
这样第一个条件就处理完了 接下来是第二个条件
随脚画了一个图
这里我们假设D=2，那么对于每个点((x,y,z))，都要向 和它相邻的竖轴的 高度为(z-D)的那几个点各连一条inf
比如这个例子中，((x,y,4))要向((x,y+1,2))连一条边，((x,y+1,4))也要向((x,y,2))连边
这有什么用呢？假设我们割的是图中的这两条边，实际上就相当于在切糕上切了((x,y,4))和((x,y+1,1))这两个地方
这样增加了这种反向边之后，我们发现沿着蓝色路径依然可以从源点到汇点，也就是说割那两条边的方案不是一个合法割
它也确实和题意不符 因为(4-1=3>D)
这就解决了第二个限制条件
还有一个问题是我做题的时候想到的：万一最小割的方案在一条链上割了两条边怎么办？
实际上这种情况是不会出现的，画一画就能发现，如果一条链上割了两条边，那么重新连上其中一条边之后一定还是个合法割
代码
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}
const int inf = 0x7fffffff;
int n, m, h, D, s, t;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int a[50][50][50], id[50][50][50], tot; // id[x][y][z]表示切糕上的(x,y,z)对应网络流里的哪个点
int now[100005], head[100005], pre[1000005], to[1000005], flow[1000005], sz = 1;
void addedge(int u, int v, int w) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v; flow[sz] = w;
}
int d[100005];
bool bfs() {
queue<int> q;
memset(d, 0, sizeof(d));
q.push(s); d[s] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (flow[i] && !d[y]) {
d[y] = d[x] + 1;
q.push(y);
}
}
}
return d[t];
}
int dfs(int x, int nowflow) {
if (!nowflow || x == t) return nowflow;
int rest = nowflow;
for (int i = now[x]; i; i = pre[i]) {
now[x] = i;
int y = to[i];
if (flow[i] && d[y] == d[x] + 1) {
int tmp = dfs(y, min(rest, flow[i]));
if (!tmp) d[y] = 0;
flow[i] -= tmp; flow[i^1] += tmp; rest -= tmp;
if (!rest) break;
}
}
return nowflow - rest;
}
int dinic() {
int ret = 0;
while (bfs()) {
for (int i = 0; i <= tot; i++) now[i] = head[i];
ret += dfs(s, inf);
}
return ret;
}
int main() {
read(n); read(m); read(h); read(D);
for (int k = 1; k <= h; k++) {
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
read(a[i][j][k]);
}
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
for (int k = 1; k <= h+1; k++) {
id[i][j][k] = ++tot;
}
}
s = 0, t = ++tot;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
addedge(s, id[i][j][1], inf); addedge(id[i][j][1], s, 0);
for (int k = 1; k <= h; k++) {
addedge(id[i][j][k], id[i][j][k+1], a[i][j][k]);
addedge(id[i][j][k+1], id[i][j][k], 0);
}
addedge(id[i][j][h+1], t, inf); addedge(t, id[i][j][h+1], 0);
for (int l = 0; l < 4; l++) {
int x = i + dir[l][0], y = j + dir[l][1];
if (1 <= x && x <= n && 1 <= y && y <= m) {
for (int k = 2; k + D <= h; k++) {
addedge(id[i][j][k+D], id[x][y][k], inf);
addedge(id[x][y][k], id[i][j][k+D], 0);
}
}
}
}
printf("%d
", dinic());
return 0;
}