NKFLOW.cpp

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

const int N = 1005;

int n, m, s, t;
vector<int> adj[N];
int capa[N][N], flow[N][N], level[N];

bool bfs(int f) {
  memset(level, 0, sizeof(level));
  queue<pair<int,int>> q;
  q.push({1, s});
  while (q.size()) {
    auto [d, i] = q.front(); q.pop();
    if (level[i]) continue;
    level[i] = d;
    if (i == t) return true;
    for (auto &j : adj[i]) {
      if (!level[j] && capa[i][j] - flow[i][j] >= f) {
        q.push({d + 1, j});
      }
    }
  }
  return false;
}

bool dfs(int i, int f) {
  if (i == t) return true;
  for (auto &j : adj[i]) {
    if (level[j] == level[i] + 1 && capa[i][j] - flow[i][j] >= f) {
      flow[i][j] += f;
      flow[j][i] -= f;
      if (dfs(j, f)) return true;
      flow[i][j] -= f;
      flow[j][i] += f;
    }
  }
  return false;
}

int main() {
  cin >> n >> m >> s >> t;
  for (int i = 1; i <= m; i++) {
    int u, v, c;
    cin >> u >> v >> c;
    adj[u].push_back(v);
    adj[v].push_back(u);
    capa[u][v] += c;
    // capa[v][u] += c;
  }
  int ans = 0;
  for (int f = (1 << 30); f; f >>= 1) {
    while (bfs(f)) {
      while (dfs(s, f)) ans += f;
    }
  }
  cout << ans << '\n';
}