結果

問題 No.3668 Minimum Cut
コンテスト
ユーザー テナガザル
提出日時 2026-09-04 22:50:47
言語 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  
実行時間 -
コード長 1,872 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,862 ms
コンパイル使用メモリ 209,984 KB
実行使用メモリ 9,676 KB
最終ジャッジ日時 2026-09-04 23:01:51
合計ジャッジ時間 7,582 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

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

template<typename T>
class maxflow
{
  struct edge {int to, rep; T cap; edge(int t, int r, T c) : to(t), rep(r), cap(c) {}};
  std::vector<std::vector<edge>> g;
  std::vector<int> dis, id;
public:
  maxflow(int n) : g(n), id(n), dis(n) {}
  void add_edge(int s, int t, T f)
  {
    g[s].push_back({t, (int)g[t].size() + (s == t), f});
    g[t].push_back({s, (int)g[s].size() - 1, 0});
  }
  T flow(int s, int t)
  {
    T ret = 0;
    while (bfs(s, t))
    {
      id.assign(id.size(), 0);
      ret += path(s, t, T((1LL << 60) | (1 << 30)));
    }
    return ret;
  }
private:
  bool bfs(int s, int t)
  {
    dis.assign(g.size(), g.size());
    dis[s] = 0;
    std::queue<int> q;
    for (q.push(s); !q.empty(); q.pop())
    {
      int now = q.front();
      for (auto &v : g[now])
      {
        if (v.cap > 0 && dis[v.to] > dis[now] + 1)
        {
          dis[v.to] = dis[now] + 1;
          q.push(v.to);
        }
      }
    }
    return dis[t] < g.size();
  }
  T path(int s, int t, T lim)
  {
    if (s == t) return lim;
    T now = 0;
    for (int &i = id[t]; i < g[t].size(); ++i)
    {
      auto &e = g[t][i], &re = g[e.to][e.rep];
      if (re.cap <= 0 || dis[e.to] >= dis[t] || dis[e.to] < 0) continue;
      T tmp = path(s, e.to, std::min(lim - now, re.cap));
      if (tmp == 0) continue;
      e.cap += tmp;
      re.cap -= tmp;
      now += tmp;
      if (now >= lim) break;
    }
    return now;
  }
};

using namespace std;

int main()
{
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  --s, --t;
  maxflow<long long> mf(n);
  for (int i = 0; i < m; ++i)
  {
    int u, v, c;
    cin >> u >> v >> c;
    --u,--v;
    mf.add_edge(u, v, c);
  }
  cout << mf.flow(s, t) << endl;
}
0