結果

問題 No.3668 Minimum Cut
コンテスト
ユーザー 👑 みうね
提出日時 2026-08-04 13:01:38
言語 C++23
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 786 ms / 2,000 ms
+ 515µs
コード長 2,506 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,552 ms
コンパイル使用メモリ 201,656 KB
実行使用メモリ 8,096 KB
最終ジャッジ日時 2026-09-04 22:00:42
合計ジャッジ時間 6,050 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

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

vector<vector<Edge>> G;
vector<int> level;
vector<int> iter;

void add_edge(int from, int to, long long cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0LL, (int)G[from].size() - 1});
}

// 容量が delta 以上の辺だけを使ってBFS
bool bfs(int s, int t, long long delta) {
    fill(level.begin(), level.end(), -1);
    level[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto& e : G[v]) {
            if (e.cap >= delta && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
    return level[t] >= 0;
}

// 容量が delta 以上の辺だけを使ってDFS
long long dfs(int v, int t, long long f, long long delta) {
    if (v == t) return f;
    for (int& i = iter[v]; i < G[v].size(); i++) {
        Edge& e = G[v][i];
        if (e.cap >= delta && level[v] < level[e.to]) {
            long long d = dfs(e.to, t, min(f, e.cap), delta);
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int main() {
    // 入出力を極限まで高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, S, T;
    if (!(cin >> N >> M >> S >> T)) return 0;
    
    G.resize(N + 1);
    level.resize(N + 1);
    iter.resize(N + 1);
    
    long long max_cap = 0;
    for (int i = 0; i < M; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        add_edge(u, v, c);
        if (c > max_cap) max_cap = c;
    }
    
    long long flow = 0;
    
    // 最大容量を超えない最大の2のべき乗を計算
    long long delta = 1;
    while (delta <= max_cap) delta *= 2;
    delta /= 2;

    // 容量スケーリングによる最大流計算
    while (delta > 0) {
        while (bfs(S, T, delta)) {
            fill(iter.begin(), iter.end(), 0);
            long long f;
            while ((f = dfs(S, T, INF, delta)) > 0) {
                flow += f;
            }
        }
        delta /= 2; // しきい値を半分にする
    }
    
    cout << flow << "\n";
    return 0;
}
0