FFLOW.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5005;

int n, m, src, snk;
vector<int> adj[N];
int capa[N][N], flow[N][N], level[N], iter[N];

bool bfs(int lim) {
  memset(level, 0, sizeof(level));
  queue<int> q; q.push(src);
  level[src] = 1;
  while (q.size()) {
    int u = q.front(); q.pop();
    if (u == snk) return 1;
    for (auto v : adj[u]) {
      if (!level[v] && capa[u][v] - flow[u][v] >= lim) {
        q.push(v);
        level[v] = level[u] + 1;
      }
    }
  }
  return 0;
}

bool dfs(int u, int lim) {
  if (u == snk) return 1;
  for (; iter[u] < adj[u].size(); iter[u]++) {
    int v = adj[u][iter[u]];
    if (level[v] == level[u] + 1) {
      if (capa[u][v] - flow[u][v] >= lim) {
        if (dfs(v, lim)) {
          flow[u][v] += lim;
          flow[v][u] -= lim;
          return 1;
        }
      }
    }
  }
  return 0;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  src = 1; snk = n;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back(v);
    adj[v].push_back(u);
    capa[u][v] += w;
    capa[v][u] += w;
  }
  int sum = 0, lim = (1LL << 60);
  while (lim) {
    if (!bfs(lim)) lim >>= 1;
    else {
      memset(iter, 0, sizeof(iter));
      while (dfs(src, lim)) sum += lim;
    }
  }
  cout << sum << '\n';
}