题目大意：有一个$n\times m$的切糕，每一个位置的高度可以在$[1,k]$之间，每个高度有一个代价，要求四联通的两个格子之间高度最多相差$D$，问可行的最小代价。$n,m,k,D\leqslant 40$
题解：网络流，不考虑相差为$D$的条件时，可以给每个位置建一个点，源点连向高度为$1$的点容量为$\infty$，高度为$i$的点连向这个位置高度为$i+1$的点，容量为代价，高度为$k$的连向汇点，容量为代价。跑最小割。
考虑相差为$D$的条件，可以对于相邻的两个点$A,B$，连接$A_i\to B_{i-D}$的容量为$\infty$的边这样就强制限定两个点的最小割必须相距小于等于$D$，跑最小割即可
卡点：加边的时候多加了$k$倍，导致又$TLE$又$RE$
C++ Code：
#include <cstdio>
#include <cctype>
#include <algorithm>
const int inf = 0x3f3f3f3f; namespace std {
struct istream {
#define M (1 << 24 | 3)
char buf[M], *ch = buf - 1;
inline istream() { fread(buf, 1, M, stdin); }
inline istream& operator >> (int &x) {
while (isspace(*++ch));
for (x = *ch & 15; isdigit(*++ch); ) x = x * 10 + (*ch & 15);
return *this;
}
#undef M
} cin;
struct ostream {
#define M (1 << 10 | 3)
char buf[M], *ch = buf - 1;
inline ostream& operator << (int x) {
if (!x) {*++ch = '0'; return *this;}
static int S[20], *top; top = S;
while (x) {*++top = x % 10 ^ 48; x /= 10;}
for (; top != S; --top) *++ch = *top;
return *this;
}
inline ostream& operator << (const char x) {*++ch = x; return *this;}
inline ~ostream() { fwrite(buf, 1, ch - buf + 1, stdout); }
#undef M
} cout;
} namespace Network_Flow {
const int maxn = 50 * 50 * 50, maxm = maxn * 6; int lst[maxn], head[maxn], cnt = 1;
struct Edge {
int to, nxt, w;
} e[maxm << 1];
void addedge(int a, int b, int c) {
e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;
e[++cnt] = (Edge) { a, head[b], 0 }; head[b] = cnt;
} int st, ed, n, MF;
int GAP[maxn], dis[maxn], q[maxn], h, t;
void init() {
GAP[dis[q[h = t = 0] = ed] = 1] = 1;
for (int i = st; i <= ed; ++i) lst[i] = head[i];
while (h <= t) {
int u = q[h++];
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (!dis[v]) {
++GAP[dis[v] = dis[u] + 1];
q[++t] = v;
}
}
}
}
int dfs(int u, int low) {
if (!low || u == ed) return low;
int w, res = 0;
for (int &i = lst[u], v; i; i = e[i].nxt) if (e[i].w) {
v = e[i].to;
if (dis[u] == dis[v] + 1) {
w = dfs(v, std::min(low, e[i].w));
res += w, low -= w;
e[i].w -= w, e[i ^ 1].w += w;
if (!low) return res;
}
}
if (!--GAP[dis[u]]) dis[st] = n + 1;
++GAP[++dis[u]], lst[u] = head[u];
return res;
}
void ISAP(int S, int T) {
st = S, ed = T, n = T - S + 1;
init(); while (dis[st] <= n) MF += dfs(st, inf);
}
} int n, m, h, D;
int v[50][50][50];
int pos[50][50][50], idx, st, ed; void addedge(int x, int y, int z, int w) {
for (int i = D + 1; i <= h; ++i)
Network_Flow::addedge(pos[x][y][i], pos[z][w][i - D], inf);
}
int main() {
std::cin >> n >> m >> h >> D;
for (int i = 1; i <= h; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= m; ++k) {
pos[j][k][i] = ++idx;
std::cin >> v[j][k][i];
}
st = 0, ed = ++idx;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= h; ++k) {
if (k == 1) Network_Flow::addedge(st, pos[i][j][k], inf);
if (k == h) Network_Flow::addedge(pos[i][j][k], ed, v[i][j][k]);
else Network_Flow::addedge(pos[i][j][k], pos[i][j][k + 1], v[i][j][k]);
}
if (i != 1) addedge(i, j, i - 1, j);
if (i != n) addedge(i, j, i + 1, j);
if (j != 1) addedge(i, j, i, j - 1);
if (j != n) addedge(i, j, i, j + 1);
}
Network_Flow::ISAP(st, ed);
std::cout << Network_Flow::MF << '\n';
return 0;
}