結果

問題 No.3668 Minimum Cut
コンテスト
ユーザー TKTYI
提出日時 2026-08-27 13:07:46
言語 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  
実行時間 1,058 ms / 2,000 ms
+ 320µs
コード長 2,686 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,555 ms
コンパイル使用メモリ 360,724 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-09-04 22:55:29
合計ジャッジ時間 8,855 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct max_flow{
  struct edge {
    int from, to;
    T cap, flow;
  };
  int N;
  vector<edge> es;
  max_flow(int _N) : N(_N) {}
  void add_edge(int from, int to, T cap) {
    es.emplace_back(edge{from, to, cap, 0});
  }
  T flow(int s, int t) {
    assert(s != t);
    unsigned long long total_flow = 0;
    for (int l = 63; l >= 0; l--) {
      while (1) {
        vector<int> D(N, N);
        vector<vector<int>> E(N);
        for (auto e : es) {
          if ((e.cap - e.flow) >> l) E[e.from].emplace_back(e.to);
          if (e.flow >> l) E[e.to].emplace_back(e.from);
        }
        queue<int> Q;
        Q.emplace(s);
        D[s] = 0;
        while (!Q.empty()) {
          int v = Q.front(); Q.pop();
          for (auto u : E[v]) if (D[u] > D[v] + 1) {
            D[u] = D[v] + 1;
            Q.emplace(u);
          }
        }
        if (D[t] == N) break;
        E.assign(N, {});
        for (int i = 0; i < es.size(); i++) {
          auto e = es[i];
          if (((e.cap - e.flow) >> l) && D[e.from] + 1 == D[e.to]) E[e.from].emplace_back(i);
          if ((e.flow >> l) && D[e.from] == D[e.to] + 1) E[e.to].emplace_back(- i - 1);
        }
        vector<int> idx(N);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int i, int j) {return D[i] < D[j];});
        while (1) {
          vector<T> DP(N);
          vector<int> P(N);
          DP[s] = numeric_limits<T>::max();
          for (auto v : idx) {
            for (auto i : E[v]) {
              if (i >= 0) {
                if (DP[es[i].to] < min(DP[v], es[i].cap - es[i].flow)) {
                  DP[es[i].to] = min(DP[v], es[i].cap - es[i].flow);
                  P[es[i].to] = i;
                }
              }
              else if (DP[es[- i - 1].from] < min(DP[v], es[- i - 1].flow)) {
                DP[es[- i - 1].from] = min(DP[v], es[- i - 1].flow);
                P[es[- i - 1].from] = i;
              }
            }
          }
          if (!DP[t]) break;
          total_flow += DP[t];
          int v = t;
          while (v != s) {
            int i = P[v];
            if (i >= 0) {
              v = es[i].from;
              es[i].flow += DP[t];
            }
            else {
              v = es[- i - 1].to;
              es[- i - 1].flow -= DP[t];
            }
          }
        }
      }
    }
    return total_flow;
  }          
};
int main() {
  int N, M, S, T;
  cin >> N >> M >> S >> T;
  S--; T--;
  max_flow<long long> G(N);
  while (M--) {
    int u, v, c;
    cin >> u >> v >> c;
    u--; v--;
    G.add_edge(u, v, c);
  }
  cout << G.flow(S, T) << endl;
}
0