Luogu P3227. [HNOI2013] Cut Cake

Original link: https://www.shuizilong.com/house/archives/luogu-p3227-hnoi2013%E5%88%87%E7%B3%95/

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

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.