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

• 問題: No.3668 Minimum Cut
• ユーザー: miie
• 提出日時: 2026-11-09 17:37:49
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 38 ms / 2,000 ms
• コード長: 3,463 bytes
• コンパイル時間: 2,680 ms
• コンパイル使用メモリ: 343,492 KB
• 実行使用メモリ: 9,900 KB
• 最終ジャッジ日時: 2026-11-09 17:37:55
• 合計ジャッジ時間: 5,491 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

// Generated with assistance from ChatGPT (OpenAI).
// Experimental Sorting Flow variant based on arXiv:1302.3035v1.
// The claimed O(M sqrt(N)) bound is not established here.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SortingFlow {
    struct Edge {
        int from, to, next_in;
        ll cap;
    };
    int n;
    vector<Edge> edges;
    vector<int> in_head;

    explicit SortingFlow(int n, int m = 0) : n(n), in_head(n, -1) {
        edges.reserve(2 * m);
    }
    void add_edge(int u, int v, ll cap) {
        int k = (int)edges.size();
        edges.push_back({u, v, in_head[v], cap});
        in_head[v] = k;
        edges.push_back({v, u, in_head[u], 0});
        in_head[u] = k + 1;
    }

    ll flow(int s, int t) {
        if (s == t) return 0;
        vector<ll> excess(n, 0);
        // Initial preflow: saturate original outgoing edges of s.
        for (int k = 0; k < (int)edges.size(); k += 2) {
            if (edges[k].from != s) continue;
            ll x = edges[k].cap;
            edges[k].cap -= x;
            edges[k ^ 1].cap += x;
            excess[edges[k].to] += x;
            excess[s] -= x;
        }

        vector<int> seen(n, 0), done(n, 0), bfs_order(n);
        vector<int> first(n), last(n), next_ord(edges.size());
        int stamp = 0;
        while (true) {
            ++stamp;
            fill(first.begin(), first.end(), -1);
            int h = 0, z = 0;
            bfs_order[z++] = t;
            seen[t] = stamp;
            bool active = false;

            // Reverse BFS; all registered arcs go to earlier BFS vertices.
            while (h < z) {
                int v = bfs_order[h++];
                done[v] = stamp;
                if (v != s && v != t && excess[v] > 0) active = true;
                for (int e = in_head[v]; e != -1; e = edges[e].next_in) {
                    if (edges[e].cap == 0) continue;
                    int u = edges[e].from;
                    if (done[u] == stamp) continue;
                    next_ord[e] = -1;
                    if (first[u] == -1) first[u] = e;
                    else next_ord[last[u]] = e;
                    last[u] = e;
                    if (seen[u] != stamp) {
                        seen[u] = stamp;
                        bfs_order[z++] = u;
                    }
                }
            }
            if (!active) break;

            // Reverse BFS order is a topological order of the chosen DAG.
            // Each vertex is discharged once, without an active deque.
            for (int i = z - 1; i >= 0; --i) {
                int v = bfs_order[i];
                if (v == s || v == t || excess[v] == 0) continue;
                for (int e = first[v]; e != -1 && excess[v] > 0;
                     e = next_ord[e]) {
                    ll x = min(excess[v], edges[e].cap);
                    if (x == 0) continue;
                    edges[e].cap -= x;
                    edges[e ^ 1].cap += x;
                    excess[v] -= x;
                    excess[edges[e].to] += x;
                }
            }
        }
        return excess[t];
    }
};

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, M);
    for (int i = 0; i < M; ++i) {
        int u, v; ll c;
        cin >> u >> v >> c;
        mf.add_edge(u - 1, v - 1, c);
    }
    cout << mf.flow(S, T) << '\n';
}