每层每个位置向下一层这个位置连边，流量为下一层这个位置的\(f\)，源点向第一层连，流量第一层每个位置的费用，最后一层向汇点连，流量\(INF\)。
这样就得到了\(P*Q\)条链，不考虑\(D\)的限制的话求最小割就是答案。 现在加入限制。#include#include #include #define INF 2147483647using namespace std;const int MAXN = 900010;const int MAXM = 2000010;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * w;}struct Edge{ int next, to, rest;}e[MAXM];int s, t, num = 1, n, m, a, b, c, p, q, r, d, f[45][45][45];int head[MAXN];inline void Add(int from, int to, int flow){ e[++num] = (Edge){ head[from], to, flow }; head[from] = num; e[++num] = (Edge){ head[to], from, 0 }; head[to] = num;}int level[MAXN], now, sum;queue Q;int re(){ memset(level, 0, sizeof level); while(Q.size()) Q.pop(); Q.push(s); level[s] = 1; while(Q.size()){ now = Q.front(); Q.pop(); for(int i = head[now]; i; i = e[i].next) if(e[i].rest && !level[e[i].to]){ level[e[i].to] = level[now] + 1; Q.push(e[i].to); } } return level[t];}int findflow(int u, int flow){ if(!flow || u == t) return flow; int f = 0, t; for(int i = head[u]; i; i = e[i].next){ if(e[i].rest && level[e[i].to] == level[u] + 1){ f += (t = findflow(e[i].to, min(flow - f, e[i].rest))); e[i].rest -= t; e[i ^ 1].rest += t; } } if(!f) level[u] = 0; return f;}int dinic(){ int ans = 0; while(re()) ans += findflow(s, INF); return ans;}int id(int k, int i, int j){ if(!k) return s; return (k - 1) * (p * q) + (i - 1) * q + j;}int L[] = {233, -1, 1, 0, 0}, R[] = {666, 0, 0, -1, 1};int main(){ p = read(); q = read(); r = read(); d = read(); s = 899999; t = 900000; for(int i = 1; i <= p; ++i) for(int j = 1; j <= q; ++j) Add(id(r, i, j), t, INF); for(int k = 1; k <= r; ++k) for(int i = 1; i <= p; ++i) for(int j = 1; j <= q; ++j) Add(id(k - 1, i, j), id(k, i, j), read()); for(int i = 1; i <= p; ++i) for(int j = 1; j <= q; ++j) for(int k = 1; k <= 4; ++k){ int x = i + L[k], y = j + R[k]; if(!x || !y || x > p || y > q) continue; for(int o = d + 1; o <= r; ++o) Add(id(o, i, j), id(o - d, x, y), INF); } printf("%d\n", dinic()); return 0;}