#1174925 (C++23) No.3668 Minimum Cut

• 問題: No.3668 Minimum Cut
• ユーザー: 👑 みうね
• 提出日時: 2026-08-04 03:24:41
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 456 ms / 2,000 ms
• コード長: 8,442 bytes
• コンパイル時間: 1,590 ms
• コンパイル使用メモリ: 209,680 KB
• 実行使用メモリ: 9,768 KB
• 最終ジャッジ日時: 2026-09-04 22:00:22
• 合計ジャッジ時間: 9,270 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 39

ソースコード

#include <cstdint>
#include <iostream>
#include <vector>

// BEGIN expanded hlpp.hpp

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

class HighestLabelPreflowPush {
public:
    using i64 = std::int64_t;

    struct Edge {
        int to;
        int rev;
        i64 cap;
    };

    struct OriginalEdge {
        int from;
        int index;
        int to;
        i64 cap;
    };

    explicit HighestLabelPreflowPush(int n, bool use_gap = true, bool use_global_relabel = true)
        : n_(n), graph_(n), use_gap_(use_gap), use_global_relabel_(use_global_relabel) {}

    void addEdge(int from, int to, i64 cap) {
        assert(0 <= from && from < n_);
        assert(0 <= to && to < n_);
        assert(from != to);
        assert(cap >= 0);
        const int from_index = static_cast<int>(graph_[from].size());
        const int to_index = static_cast<int>(graph_[to].size());
        graph_[from].push_back(Edge{to, to_index, cap});
        graph_[to].push_back(Edge{from, from_index, 0});
        original_.push_back(OriginalEdge{from, from_index, to, cap});
    }

    i64 maxFlow(int source, int sink) {
        assert(source != sink);
        source_ = source;
        sink_ = sink;
        const int height_limit = 2 * n_ + 1;
        height_.assign(n_, 0);
        current_.assign(n_, 0);
        count_.assign(height_limit + 1, 0);
        excess_.assign(n_, 0);
        active_.assign(n_, false);
        buckets_.assign(height_limit + 1, {});
        highest_ = 0;
        work_ = 0;

        height_[source_] = n_;
        for (Edge &edge : graph_[source_]) {
            if (edge.cap == 0) continue;
            const i64 pushed = edge.cap;
            edge.cap = 0;
            graph_[edge.to][edge.rev].cap += pushed;
            excess_[source_] -= pushed;
            excess_[edge.to] += pushed;
        }

        globalRelabel();
        while (true) {
            const int vertex = popHighest();
            if (vertex == -1) break;
            discharge(vertex);
            if (use_global_relabel_ && work_ >= globalRelabelFrequency()) {
                globalRelabel();
            }
        }
        return excess_[sink_];
    }

    std::vector<char> sourceSide() const {
        std::vector<char> reached(n_, false);
        std::queue<int> que;
        reached[source_] = true;
        que.push(source_);
        while (!que.empty()) {
            const int vertex = que.front();
            que.pop();
            for (const Edge &edge : graph_[vertex]) {
                if (edge.cap == 0 || reached[edge.to]) continue;
                reached[edge.to] = true;
                que.push(edge.to);
            }
        }
        return reached;
    }

    i64 cutCapacity(const std::vector<char> &source_side) const {
        i64 result = 0;
        for (const OriginalEdge &edge : original_) {
            if (source_side[edge.from] && !source_side[edge.to]) {
                result += edge.cap;
            }
        }
        return result;
    }

private:
    int n_;
    int source_ = -1;
    int sink_ = -1;
    std::vector<std::vector<Edge>> graph_;
    std::vector<OriginalEdge> original_;
    bool use_gap_;
    bool use_global_relabel_;

    std::vector<int> height_;
    std::vector<int> current_;
    std::vector<int> count_;
    std::vector<i64> excess_;
    std::vector<char> active_;
    std::vector<std::vector<int>> buckets_;
    int highest_ = 0;
    std::int64_t work_ = 0;

    std::int64_t globalRelabelFrequency() const {
        std::int64_t residual_edges = 0;
        for (const auto &edges : graph_) residual_edges += static_cast<std::int64_t>(edges.size());
        return std::max<std::int64_t>(1, 4 * residual_edges + n_);
    }

    void activate(int vertex) {
        if (vertex == source_ || vertex == sink_ || excess_[vertex] <= 0 || active_[vertex]) return;
        active_[vertex] = true;
        buckets_[height_[vertex]].push_back(vertex);
        highest_ = std::max(highest_, height_[vertex]);
    }

    int popHighest() {
        while (highest_ >= 0) {
            while (!buckets_[highest_].empty()) {
                const int vertex = buckets_[highest_].back();
                buckets_[highest_].pop_back();
                if (!active_[vertex] || height_[vertex] != highest_ || excess_[vertex] <= 0) continue;
                active_[vertex] = false;
                return vertex;
            }
            --highest_;
        }
        return -1;
    }

    void push(int vertex, Edge &edge) {
        const i64 amount = std::min(excess_[vertex], edge.cap);
        if (amount == 0) return;
        edge.cap -= amount;
        graph_[edge.to][edge.rev].cap += amount;
        excess_[vertex] -= amount;
        excess_[edge.to] += amount;
        activate(edge.to);
    }

    void applyGap(int empty_height, int current_vertex) {
        if (!use_gap_ || empty_height >= n_ || count_[empty_height] != 0) return;
        const int dead_height = n_ + 1;
        for (int vertex = 0; vertex < n_; ++vertex) {
            if (vertex == source_ || vertex == sink_) continue;
            if (height_[vertex] <= empty_height || height_[vertex] >= dead_height) continue;
            --count_[height_[vertex]];
            height_[vertex] = dead_height;
            ++count_[height_[vertex]];
            current_[vertex] = 0;
            if (vertex != current_vertex) {
                active_[vertex] = false;
                activate(vertex);
            }
        }
    }

    void relabel(int vertex) {
        const int old_height = height_[vertex];
        int new_height = 2 * n_ + 1;
        for (const Edge &edge : graph_[vertex]) {
            if (edge.cap > 0) new_height = std::min(new_height, height_[edge.to] + 1);
        }
        assert(new_height <= 2 * n_);
        --count_[old_height];
        height_[vertex] = new_height;
        ++count_[new_height];
        current_[vertex] = 0;
        applyGap(old_height, vertex);
        highest_ = std::max(highest_, height_[vertex]);
    }

    void discharge(int vertex) {
        while (excess_[vertex] > 0) {
            if (current_[vertex] == static_cast<int>(graph_[vertex].size())) {
                relabel(vertex);
                work_ += static_cast<std::int64_t>(graph_[vertex].size()) + 1;
                continue;
            }
            Edge &edge = graph_[vertex][current_[vertex]];
            ++work_;
            if (edge.cap > 0 && height_[vertex] == height_[edge.to] + 1) {
                push(vertex, edge);
            } else {
                ++current_[vertex];
            }
        }
    }

    void globalRelabel() {
        const int dead_height = n_ + 1;
        std::fill(height_.begin(), height_.end(), dead_height);
        std::fill(current_.begin(), current_.end(), 0);

        std::queue<int> que;
        height_[sink_] = 0;
        que.push(sink_);
        while (!que.empty()) {
            const int vertex = que.front();
            que.pop();
            for (const Edge &edge : graph_[vertex]) {
                const Edge &reverse = graph_[edge.to][edge.rev];
                if (reverse.cap == 0 || height_[edge.to] != dead_height) continue;
                height_[edge.to] = height_[vertex] + 1;
                que.push(edge.to);
            }
        }
        height_[source_] = n_;

        std::fill(count_.begin(), count_.end(), 0);
        for (int vertex = 0; vertex < n_; ++vertex) ++count_[height_[vertex]];
        for (auto &bucket : buckets_) bucket.clear();
        std::fill(active_.begin(), active_.end(), false);
        highest_ = 0;
        for (int vertex = 0; vertex < n_; ++vertex) activate(vertex);
        work_ = 0;
    }
};
// END expanded hlpp.hpp

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

    int n, m, source, sink;
    if (!(std::cin >> n >> m >> source >> sink)) return 0;
    --source;
    --sink;

    HighestLabelPreflowPush flow(n);
    for (int i = 0; i < m; ++i) {
        int from, to;
        std::int64_t capacity;
        std::cin >> from >> to >> capacity;
        flow.addEdge(from - 1, to - 1, capacity);
    }

    const std::int64_t answer = flow.maxFlow(source, sink);
    const std::vector<char> source_side = flow.sourceSide();
    if (source_side[sink] || flow.cutCapacity(source_side) != answer) return 1;
    std::cout << answer << '\n';
    return 0;
}