NKFLOW.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];

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

int dfs(int u, int lim) {
  if (u == snk) return lim;
  for (auto v : adj[u]) {
    if (level[v] > level[u]) {
      if (capa[u][v] - flow[u][v] > 0) {
        int f = dfs(v, min(lim, capa[u][v] - flow[u][v]));
        if (f > 0) {
          flow[u][v] += f;
          flow[v][u] -= f;
          return f;
        }
      }
    }
  }
  return 0;
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m >> src >> snk;
  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;
  while (1) {
    bfs();
    if (!level[snk]) break;
    for (int f; (f = dfs(src, LLONG_MAX)) > 0; ) sum += f;
  }
  cout << sum << '\n';
}