最小割模板。
题意：你要在一个三维点阵的每个竖条中删去一个点，使得删去的点权和最小。
且相邻(四联通)的两竖条之间删的点的z坐标之差的绝对值不超过D。
解：
首先把这些都串起来，点边转化，就变成最小割了对吧。
那么限制条件怎么处理呢？
我们知道在最小割中流量为INF的边是割不断的，以此来连边，使得相邻的割点超过D不合法。
具体来说：把相邻的两条链中，差距刚好为D的点连起来。从上往下连INF。
这是D = 1的一个连边实例。
可以发现，我们割两个在同一高度的边是没问题的。
如果高度相差1也没问题。
如果左边的高2格，那么会被红色的边限制;如果右边的高2格又会被蓝色的边限制。
所以这样连边就能够满足限制条件了。
然后跑最小割即可。
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring> const int N = , M = , INF = 0x3f3f3f3f;
const int dx[] = {, , -, };
const int dy[] = {, , , -}; struct Edge {
int nex, v, c;
}edge[M << ]; int top = ; int e[N], d[N], m, n;
std::queue<int> Q; inline void add(int x, int y, int z) {
top++;
edge[top].v = y;
edge[top].c = z;
edge[top].nex = e[x];
e[x] = top; top++;
edge[top].v = x;
edge[top].c = ;
edge[top].nex = e[y];
e[y] = top;
return;
} inline bool BFS(int s, int t) {
memset(d, , sizeof(d));
d[s] = ;
Q.push(s);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[y]) {
continue;
}
d[y] = d[x] + ;
Q.push(y);
}
}
return d[t];
} int DFS(int x, int t, int maxF) {
if(x == t) {
return maxF;
}
int ans = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[x] + != d[y]) {
continue;
}
int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
if(!temp) {
d[y] = INF;
}
ans += temp;
edge[i].c -= temp;
edge[i ^ ].c += temp;
if(ans == maxF) {
break;
}
}
return ans;
} inline int solve(int s, int t) {
int ans = ;
while(BFS(s, t)) {
ans += DFS(s, t, INF);
}
return ans;
} inline int id(int x, int y, int z) {
return z * n * m + (x - ) * m + y;
} int main() {
int r, D, x;
scanf("%d%d%d%d", &n, &m, &r, &D);
for(int k = ; k <= r; k++) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
scanf("%d", &x);
add(id(i, j, k - ), id(i, j, k), x);
}
}
}
int s = n * m * (r + ) + ;
int t = s + ;
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
for(int k = D; k <= r; k++) {
for(int dir = ; dir < ; dir++) {
x = i + dx[dir];
int y = j + dy[dir];
if(x && y && x <= n && y <= m) {
add(id(i, j, k), id(x, y, k - D), INF);
}
}
}
add(s, id(i, j, ), INF);
add(id(i, j, r), t, INF);
}
} int ans = solve(s, t);
printf("%d", ans);
return ;
}
AC代码