Download Speed

#include <bits/stdc++.h>
using namespace std;
// clang-format off
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#ifdef DO_DBG
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> using v = vector<T>;
template <typename T> using us = unordered_set<T>;
template <typename K, typename V> using um = unordered_map<K, V>;
template <typename K, typename V> using p = pair<K, V>;
template <typename T> using pq = priority_queue<T>;
template <typename T> using nl = numeric_limits<T>;
constexpr int MOD = 1e9 + 7;
constexpr int INF = 1e9;
constexpr ld EPS = 1e-9;
// fancy 
#define loopi(n) for (auto i : std::views::iota(0, n))
#define loopj(n) for (int j = 0; j < n; j++)
#define loopk(n) for (int k = 0; k < n; k++)
#define loopz(n) for (int z = 0; z < n; z++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sq(x) ((x) * (x))
template <typename... Args> void read(Args&... args) { ((cin >> args), ...); }
#define d(...) int __VA_ARGS__; read(__VA_ARGS__);
#define dv(x, n) vector<int> x(n); for (int i = 0; i < n; i++) cin >> x[i];
#define dvl(x, n) vector<long long> x(n); for (int i = 0; i < n; i++) cin >> x[i];
#define dvd(x, n) vector<double> x(n); for (int i = 0; i < n; i++) cin >> x[i];
template <typename T> struct Mat {
  int n, m;
  std::vector<T> a;
  Mat(int n, int m, T val = T()) : n(n), m(m), a(n * m, val) {}
  T &operator()(int i, int j) { return a[i * m + j]; }
  const T &operator()(int i, int j) const { return a[i * m + j]; }
};
// clang-format on

template <class F> struct y_combinator {
  F f;
  template <class... Args> decltype(auto) operator()(Args &&...args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};

struct edge {
  int to, w, rev;
};

int main() {
  fastio;
  d(n, m);

  v<v<edge>> adj(n);
  ll threshold = 0;
  while (m--) {
    d(a, b, c);
    a--;
    b--;
    threshold += c;
    adj[a].emplace_back(b, c, adj[b].size());
    // reverse edges for the ford-fulkerson algorithm
    adj[b].emplace_back(a, 0, adj[a].size() - 1);
    // the last field, rev is an optimization so we dont need to find the
    // reverse edges with find_if
  }

  int found_min_w = 0;
  ll total_flow = 0;
  do {
    v<bool> vis(n);
    // if we just want to calculate min_w we could do bottom up
    // but since we want to know the min_flow before bubbling up
    // (because we want to decrease w) we pass the flow from the top
    // to the bottom
    // this also allows us to simplify the base case a bit, since we can recurse
    // into the last node

    found_min_w = y_combinator([&](auto dfs, int node, int flow_td) -> int {
      if (node == n - 1)
        return flow_td;
      vis[node] = true;
      for (auto &[c, w, rev] : adj[node]) {
        if (w >= threshold && !vis[c]) {
          auto new_flow = dfs(c, min(w, flow_td));
          if (new_flow) {
            // we found a path
            // we know new_flow is the minimum weight, since
            // w was considered for each edge when recursing top down
            w -= new_flow;
            // increment the reverse edge
            // find_if(all(adj[c]), [node](auto &p) {
            //   return p.first == node;
            // })->second += new_flow;
            adj[c][rev].w += new_flow;
            return new_flow;
          }
        }
      }
      return 0;
    })(0, nl<int>::max());
    total_flow += found_min_w;
    if (!found_min_w)
      threshold /= 2;
    // scaling algorithm ^
  } while (threshold);

  cout << total_flow << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED