• https://www.luogu.com.cn/problem/P3227

简单最小割~

#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;
}

Posted by xiaodao
Category: 日常