Download Speed

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

const int N = 500;
ll W[N][N];
vector<int> V[N];
int n, m;
bool Z[N];

ll dfs(int i, ll c, ll w0) {
  if (i == n-1) {
    return w0;
  }
  if (Z[i]) return 0;
  Z[i] = 1;
  for (int j : V[i]) {
    ll w = W[i][j];
    if (w >= c) {
      ll v = dfs(j,c,min(w0,w));
      if (v) {
        W[i][j] -= v;
        W[j][i] += v;
        return v;
      }
    }
  }
  return 0;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    V[a-1].push_back(b-1);
    V[b-1].push_back(a-1);
    W[a-1][b-1] += c;
  }
  ll ans = 0;
  for (ll c = 1; c >= 1; c /= 2) {
    while (1) {
      memset(Z,0,n);
      ll w = dfs(0,c,1e18);
      if (w == 0) break;
      ans += w;
    }
  }
  cout << ans << '\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