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

• 問題: No.3668 Minimum Cut
• ユーザー: miie
• 提出日時: 2026-11-09 17:17:48
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,289 ms / 2,000 ms
• コード長: 3,763 bytes
• コンパイル時間: 3,371 ms
• コンパイル使用メモリ: 359,004 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-11-09 17:17:57
• 合計ジャッジ時間: 9,237 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge7_0

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

ソースコード

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

struct SortingFlow {
    struct Edge { int to, rev; ll cap; };
    int n;
    vector<vector<Edge>> g;
    explicit SortingFlow(int n) : n(n), g(n) {}

    void add_edge(int u, int v, ll cap) {
        int i = (int)g[u].size();
        int j = (int)g[v].size();
        if (u == v) ++j;
        g[u].push_back({v, j, cap});
        g[v].push_back({u, i, 0});
    }

    ll flow(int s, int t) {
        vector<ll> ex(n, 0);
        for (int i = 0; i < (int)g[s].size(); ++i) {
            Edge &e = g[s][i];
            if (e.to == s || e.cap == 0) continue;
            ll z = e.cap;
            e.cap = 0;
            g[e.to][e.rev].cap += z;
            ex[e.to] += z;
            ex[s] -= z;
        }

        // All incoming residual edge indices (including reverse edges).
        vector<vector<pair<int, int>>> incoming(n);
        for (int u = 0; u < n; ++u)
            for (int i = 0; i < (int)g[u].size(); ++i)
                incoming[g[u][i].to].push_back({u, i});

        vector<vector<int>> ord(n);
        vector<int> state(n), ptr(n);
        vector<char> inq(n);
        while (true) {
            fill(state.begin(), state.end(), 0);
            fill(ptr.begin(), ptr.end(), 0);
            fill(inq.begin(), inq.end(), 0);
            for (auto &v : ord) v.clear();

            queue<int> bfs;
            bfs.push(t);
            state[t] = 1;
            deque<int> active;
            while (!bfs.empty()) {
                int v = bfs.front();
                bfs.pop();
                state[v] = 2;
                if (v != s && v != t && ex[v] > 0) {
                    active.push_back(v);
                    inq[v] = 1;
                }
                for (auto [u, i] : incoming[v]) {
                    if (g[u][i].cap == 0 || state[u] == 2) continue;
                    ord[u].push_back(i);
                    if (state[u] == 0) {
                        state[u] = 1;
                        bfs.push(u);
                    }
                }
            }
            if (active.empty()) break;

            ll old = ex[t];
            while (!active.empty()) {
                int v = active.front();
                active.pop_front();
                inq[v] = 0;
                while (ex[v] > 0 && ptr[v] < (int)ord[v].size()) {
                    Edge &e = g[v][ord[v][ptr[v]]];
                    if (e.cap == 0) {
                        ++ptr[v];
                        continue;
                    }
                    ll z = min(ex[v], e.cap);
                    e.cap -= z;
                    g[e.to][e.rev].cap += z;
                    ex[v] -= z;
                    ex[e.to] += z;
                    if (e.to != s && e.to != t && ex[e.to] > 0 && !inq[e.to]) {
                        active.push_front(e.to);
                        inq[e.to] = 1;
                    }
                    if (e.cap == 0) ++ptr[v];
                }
            }
            // Experimental stopping rule (not proved correct generally).
            if (ex[t] == old) break;
        }
        // Only the cut value is requested: no matching/flow reconstruction.
        return ex[t];
    }
};
// This code was generated by ChatGPT (OpenAI).
// The implementation is based on the Sorting Flow algorithm
// described in arXiv:1302.3035v1. (https://arxiv.org/html/1302.3035v1)
// The code has not been formally verified.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, S, T;
    cin >> N >> M >> S >> T;
    --S; --T;
    SortingFlow mf(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        mf.add_edge(--u, --v, c);
    }
    cout << mf.flow(S, T) << '\n';
}