Submission #57577620

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/maxflow>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)

ll read(){ll r;scanf("%lld",&r);return r;}

int main() {
    using namespace std;
    int N=read();

    atcoder::mf_graph<int> G(1 + 4 * N * N + 1);
    const int S = 0, T = 1 + 4 * N * N;
    // v \in [1,4], A[i][j] > v
    const auto _{[N](int i, int j, int v){ return (i * N + j) * 4 + v; }};

    constexpr int inf = 2 * 20 * 19 * 16 + 1; // Let inf a value greater than maximum possible cos

    // Aij > v+1 则 Aij > v
    rep(i,0,N) rep(j,0,N) rep(v,1,4) G.add_edge(_(i, j, v + 1), _(i, j, v), inf);

    // j 和 j+1相邻
    rep(i,0,N) rep(j,0,N-1) rep(v,1,5) {
      G.add_edge(_(i, j    , v), _(i, j + 1, v), 1); // v=v
      G.add_edge(_(i, j + 1, v), _(i, j    , v), 1);
      rep(u,1,v) { // v > u
        G.add_edge(_(i, j    , v), _(i, j + 1, u), 2);
        G.add_edge(_(i, j + 1, v), _(i, j    , u), 2);
      }
    }

    // i和i+1相邻
    rep(i,0,N-1) rep(j,0,N) rep(v,1,5) {
      G.add_edge(_(i    , j, v), _(i + 1, j, v), 1); // v=v
      G.add_edge(_(i + 1, j, v), _(i    , j, v), 1);
      rep(u,1,v){ // v > u
        G.add_edge(_(i    , j, v), _(i + 1, j, u), 2);
        G.add_edge(_(i + 1, j, v), _(i    , j, u), 2);
      }
    }

    // 默认非零的点增加值限制
    rep(i,0,N) rep(j,0,N){
      int A=read();
      if(A == 0) continue;
      if(A < 5) G.add_edge(_(i, j, A), T             , inf); // 保证 不满足 > A
      if(A > 1) G.add_edge(S         , _(i, j, A - 1), inf); // 保证 满足 > A-1 也就是>=A
    }

    // 最大流=最小割
    G.flow(S, T);
    // https://github.com/atcoder/ac-library/blob/master/atcoder/maxflow.hpp
    // min_cut 实现原理是dfs+有剩余容量可达性, 判断是否和S可达, 返回的是 [点]=是否可达
    const auto& cut{G.min_cut(S)};

    rep(i,0,N) {
      rep(j,0,N){
        int B{1};
        rep(v,1,5) B += cut[_(i, j, v)];
        printf("%d ",B);
      }
      printf("\n");
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘ll read()’:
Main.cpp:9:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    9 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result