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

简单的平面图最小割，难点是证这个是最小割。
代码主打的是一手对称。= =

#include <lastweapon/io>
#include <lastweapon/dijkstra>

using namespace lastweapon;

int n, s, t;

int id(int x, int y) {
    if (x == -1 || y == n) return s;
    if (x == n || y == -1) return t;
    return x*n + y;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n); s=n*n; t=s+1; sp_graph<int> G(t+1);

    REP(x, n+1) REP(y, n) G.add_edge(id(x-1,y), id(x,y), RD());
    REP(x, n) REP(y, n+1) G.add_edge(id(x,y), id(x,y-1), RD());
    REP(x, n+1) REP(y, n) G.add_edge(id(x,y), id(x-1,y), RD());
    REP(x, n) REP(y, n+1) G.add_edge(id(x,y-1), id(x,y), RD());

    cout << G.dijkstra(s, t) << endl;
}

Posted by xiaodao
Category: 日常