結果

問題 No.2328 Build Walls
コンテスト
ユーザー coindarw
提出日時 2023-05-28 15:55:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,900 bytes
コンパイル時間 4,283 ms
コンパイル使用メモリ 259,084 KB
最終ジャッジ日時 2025-02-13 14:32:11
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 1 TLE * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
using ll = long long;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); ++i)
constexpr int inf = 2000'000'000;
constexpr ll linf = 4000000000000000000ll;
constexpr ll M7 = 1000000007ll;
constexpr ll M09 = 1000000009ll;
constexpr ll M9 = 998244353ll;
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using namespace atcoder;
template <typename T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
    for (auto& e : v) os << e << " ";
    return os;
}
template <typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) noexcept {
    return os << "(" << p.first << ", " << p.second << ")";
}
#ifdef ONLINE_JUDGE
#define debug(...)
#else
#define debug(...) cerr << "<" << #__VA_ARGS__ << ">: ", debug_out(__VA_ARGS__)
template <typename T>
void debug_out(T t) {
    cerr << t << endl;
}
template <typename T, typename... Args>
void debug_out(T t, Args... args) {
    cerr << t << ", ";
    debug_out(args...);
}
#endif

template <typename Cap>
class MaxFlow {
   protected:
    int V;

    struct edge {
        int to;
        Cap cap;
        int rev;
        Cap flow = Cap(0);
        edge(int to, Cap cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    void bfs(int s) {
        std::fill(begin(level), end(level), -1);
        std::queue<int> q;
        level.at(s) = 0;
        q.push(s);

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (edge& e : G.at(v)) {
                // for (int i = 0; i < int(G.at(v).size()); i++) {
                //     edge &e = G.at(v).at(i);
                if (e.cap > 0 && level.at(e.to) < 0) {
                    level.at(e.to) = level.at(v) + 1;
                    q.push(e.to);
                }
            }
        }
    }
    Cap dfs(int v, int t, Cap f) {
        if (v == t)
            return f;
        for (int& i = iter.at(v); i < int(G.at(v).size()); i++) {
            edge& e = G.at(v).at(i);
            if (e.cap > Cap(0) && level.at(v) < level.at(e.to)) {
                Cap d = dfs(e.to, t, ((f < e.cap) ? f : e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G.at(e.to).at(e.rev).cap += d;
                    return d;
                }
            }
        }
        return Cap(0);
    }

    std::vector<std::vector<edge>> G;
    std::vector<int> iter, level;

   public:
    MaxFlow(int v) : V(v) {
        G = std::vector<std::vector<edge>>(v);
        iter = std::vector<int>(v);
        level = std::vector<int>(v);
    }

    Cap flow(int s, int t, Cap limit) {
        assert(0 <= s && s < V);
        assert(0 <= t && t < V);
        assert(limit >= Cap(0));
        Cap _flow = Cap(0);
        while (true) {
            bfs(s);
            if (level.at(t) < 0)
                return _flow;
            std::fill(begin(iter), end(iter), 0);
            Cap f;
            while ((f = dfs(s, t, limit)) > 0) {
                _flow += f;
                limit -= f;
            }
        }
    }

    Cap flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); }

    void add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < V);
        assert(0 <= to && to < V);
        assert(cap >= Cap(0));
        G.at(from).push_back(edge(to, cap, G.at(to).size()));
        G.at(to).push_back(edge(from, Cap(0), G.at(from).size() - 1));
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a = vector<vector<int>>(h - 2, vector<int>(w));
    rep(i, h - 2) {
        rep(j, w) {
            cin >> a.at(i).at(j);
            if (a.at(i).at(j) == -1)
                a.at(i).at(j) = inf;
        }
    }
    int HW = (h - 2) * w;
    mf_graph<ll> mf(HW * 2 + 2);
    const int s = HW * 2, t = HW * 2 + 1;
    const int dx[] = {1, 0, -1, 0};
    const int dy[] = {0, 1, 0, -1};
    auto vert = [&](int y, int x) { return y * w + x; };
    rep(y, h - 2) rep(x, w) {
        rep(k, 3) {
            int ny = y + dy[k], nx = x + dx[k];
            if (ny < 0 || ny >= h - 2 || nx < 0 || nx >= w)
                continue;
            mf.add_edge(vert(y, x) + HW, vert(ny, nx), inf);
        }
        mf.add_edge(vert(y, x), vert(y, x) + HW, a.at(y).at(x));
    }
    rep(i, w) {
        mf.add_edge(s, i, inf);
        mf.add_edge((h - 3) * w + i + HW, t, inf);
    }
    ll ans = mf.flow(s, t);
    if (ans >= inf)
        ans = -1;
    cout << ans << "\n";
    return 0;
}
0