Original link: https://www.shuizilong.com/house/archives/luogu-p3227-hnoi2013%E5%88%87%E7%B3%95/
Simple minimum cut~
#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, rD);
G. add_edge(u, v, INF);
}
}
}
cout << G. flow(s, t) << endl;
}
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p3227-hnoi2013%E5%88%87%E7%B3%95/
This site is only for collection, and the copyright belongs to the original author.