結果

問題 No.2328 Build Walls
ユーザー lam6er
提出日時 2025-04-16 00:48:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,397 bytes
コンパイル時間 4,766 ms
コンパイル使用メモリ 209,912 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-16 00:51:09
合計ジャッジ時間 10,414 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;

struct Edge {
    int to, rev;
    ll cap;
    Edge(int t, int r, ll c) : to(t), rev(r), cap(c) {}
};

const ll INF = 1e18;

class Dinic {
public:
    vector<vector<Edge>> graph;
    vector<int> level, iter;

    Dinic(int n) : graph(n), level(n), iter(n) {}

    void add_edge(int from, int to, ll cap) {
        graph[from].emplace_back(to, graph[to].size(), cap);
        graph[to].emplace_back(from, graph[from].size()-1, 0);
    }

    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (Edge &e : graph[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    ll dfs(int v, int t, ll f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < graph[v].size(); ++i) {
            Edge &e = graph[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    ll max_flow(int s, int t) {
        ll flow = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            ll f;
            while ((f = dfs(s, t, INF)) > 0) {
                flow += f;
                if (flow >= INF) return INF;
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    vector<vector<int>> A(H+1, vector<int>(W+1, -1));
    for (int i = 2; i <= H-1; ++i) {
        for (int j = 1; j <= W; ++j) {
            cin >> A[i][j];
        }
    }

    int nodes = 2 * H * W + 2;
    int S = 2 * H * W;
    int T = S + 1;
    Dinic dinic(nodes);

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            int in_node = (i-1)*W + (j-1);
            int out_node = in_node + H*W;

            ll cap;
            if (i == 1 || i == H) {
                cap = INF;
            } else {
                cap = (A[i][j] == -1) ? INF : A[i][j];
            }
            dinic.add_edge(in_node, out_node, cap);
        }
    }

    vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            int out_node = (i-1)*W + (j-1) + H*W;
            for (auto [di, dj] : dirs) {
                int ni = i + di;
                int nj = j + dj;
                if (ni < 1 || ni > H || nj < 1 || nj > W) continue;
                int in_adj = (ni-1)*W + (nj-1);
                dinic.add_edge(out_node, in_adj, INF);
            }
        }
    }

    for (int j = 1; j <= W; ++j) {
        int in_node = (1-1)*W + (j-1);
        dinic.add_edge(S, in_node, INF);
    }

    for (int j = 1; j <= W; ++j) {
        int out_node = (H-1)*W + (j-1) + H*W;
        dinic.add_edge(out_node, T, INF);
    }

    ll flow = dinic.max_flow(S, T);
    cout << (flow >= INF ? -1 : flow) << endl;

    return 0;
}
0