简单最小割~
#include <lastweapon/io> #include <lastweapon/maxflow> using namespace lastweapon; int P, Q, R, D, s, t; int id(int p, int q, int r) { return r*P*Q + p*Q + q; } bool inGrid(int p, int q) { return 0 <= p && p < P && 0 <= q && q < Q; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif RD(P, Q, R, D); s = P*Q*R, t = s+1; mf_graph<int> G(t+1); REP(p, P) REP(q, Q) { G.add_edge(s, id(p, q, 0), INF); } REP(r, R) REP(p, P) REP(q, Q) { int u = id(p, q, r); G.add_edge(u, r+1 != R ? id(p, q, r+1) : t, RD()); if (r >= D) { REP(i, 4) { int x = p + dx[i], y = q + dy[i]; if (!inGrid(x, y)) continue; int v = id(x, y, r-D); G.add_edge(u, v, INF); } } } cout << G.flow(s, t) << endl; }