UnKoder #06 C Infinite Network

2015/05/22 (Fri) hackerrank UnKoder グラフ 最小カット DP

問題

問題文

方針

格子点を頂点とするグラフと見て，

  • スーパーソースからコンピュータに太さ $10000$ の辺
  • 各点から近傍 $4$ 点に太さ $1$ の辺
  • 辺境の点からスーパーシンクに太さ $10000$ の辺

を張る．すると，このグラフの最小カットが答えになる． 計算量が危ないかと思ったけど蟻本の Dinic で普通に通った．

bitDPでも 解けるらしい．

実装

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    int s = 210*210;
    int t = s+1;
    Dinic g(t+1);
    dump(s,t);
    rep(i,N){
        int x,y;
        cin >> x >> y;
        x += 105;
        y += 105;
        int v = x*210+y;
        g.add_edge(s,v,10000);
    }
    rep(y,210)rep(x,210){
        int dx[] = {0,1,0,-1};
        int dy[] = {1,0,-1,0};
        int u = x*210+y;
        rep(d,4){
            int v, c;
            if(x+dx[d] >= 210 || x+dx[d] < 0 || y+dy[d] >= 210 || y+dy[d] < 0){
                v = t, c = 10000;
            } else {
                v = (x+dx[d])*210+y+dy[d], c = 1;
            }
            g.add_edge(u,v,c);
        }
    }
    cout << g.solve(s,t) << endl;
}