結果

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

ソースコード

diff #
raw source code 

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>

class Dinic {
    using i64 = std::int64_t;
    struct Edge { int to, rev; i64 cap; };
    std::vector<std::vector<Edge>> graph;
    std::vector<int> level, current;

    bool bfs(int source, int sink) {
        std::fill(level.begin(), level.end(), -1);
        std::queue<int> que;
        level[source] = 0;
        que.push(source);
        while (!que.empty()) {
            int vertex = que.front(); que.pop();
            for (const Edge &edge : graph[vertex]) {
                if (edge.cap > 0 && level[edge.to] == -1) {
                    level[edge.to] = level[vertex] + 1;
                    que.push(edge.to);
                }
            }
        }
        return level[sink] != -1;
    }

    i64 dfs(int vertex, int sink, i64 pushed) {
        if (vertex == sink) return pushed;
        for (int &index = current[vertex]; index < static_cast<int>(graph[vertex].size()); ++index) {
            Edge &edge = graph[vertex][index];
            if (edge.cap == 0 || level[edge.to] != level[vertex] + 1) continue;
            i64 result = dfs(edge.to, sink, std::min(pushed, edge.cap));
            if (result == 0) continue;
            edge.cap -= result;
            graph[edge.to][edge.rev].cap += result;
            return result;
        }
        return 0;
    }

public:
    explicit Dinic(int size) : graph(size), level(size), current(size) {}
    void addEdge(int from, int to, i64 cap) {
        int a = static_cast<int>(graph[from].size());
        int b = static_cast<int>(graph[to].size());
        graph[from].push_back({to, b, cap});
        graph[to].push_back({from, a, 0});
    }
    i64 maxFlow(int source, int sink) {
        i64 result = 0;
        const i64 infinity = std::numeric_limits<i64>::max();
        while (bfs(source, sink)) {
            std::fill(current.begin(), current.end(), 0);
            while (i64 pushed = dfs(source, sink, infinity)) result += pushed;
        }
        return result;
    }
};

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;
    Dinic flow(n);
    for (int i = 0; i < m; ++i) {
        int from, to;
        std::int64_t cap;
        std::cin >> from >> to >> cap;
        flow.addEdge(from - 1, to - 1, cap);
    }
    std::cout << flow.maxFlow(source - 1, sink - 1) << '\n';
}
0