結果

問題 No.3668 Minimum Cut
コンテスト
ユーザー 👑 みうね
提出日時 2026-08-04 12:59:17
言語 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
結果
TLE  
実行時間 -
コード長 2,141 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,517 ms
コンパイル使用メモリ 204,460 KB
実行使用メモリ 9,732 KB
最終ジャッジ日時 2026-09-04 22:00:37
合計ジャッジ時間 6,940 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

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});
}

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

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

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

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);
    
    // 多重辺を統合して容量を合算する
    map<pair<int, int>, long long> edges;
    for (int i = 0; i < M; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        edges[{u, v}] += c;
    }
    
    for (auto& p : edges) {
        add_edge(p.first.first, p.first.second, p.second);
    }
    
    cout << max_flow(S, T) << "\n";
    return 0;
}
0