Download Speed

#include <bits/stdc++.h>

using namespace std;

const int N = 5e2 + 5;
const int INF = 1e9 + 10;

int n, m;
int cap[N][N];
vector<int> g[N];
int tmp_flow;
int p[N];

long long find_flow(int s, int t) {
  memset(p, -1, sizeof(p));
  queue<pair<int, int>> q;
  q.push({s, INF});
  p[s] = -2;
  while (!q.empty()) {
    int u = q.front().first;
    int flow = q.front().second;
    q.pop();
    for (int v : g[u]) {
      if (p[v] == -1 && cap[u][v] > 0) {
        p[v] = u;
        int new_flow = min(flow, cap[u][v]);
        if (v == t) {
          tmp_flow = new_flow;
          return new_flow;
        }
        q.push({v, new_flow});
      }
    }
  }
  return 0;
}

long long max_flow(int s, int t) {
  long long flow = 0;
  while (find_flow(s, t) > 0) {
    flow += tmp_flow;
    int y = t;
    while (y != s) {
      int x = p[y];
      cap[x][y] -= tmp_flow;
      cap[y][x] += tmp_flow;
      y = p[y];
    }
  }
  return flow;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    cap[a][b] += c;
    if (a != b) {
      g[a].emplace_back(b);
      g[b].emplace_back(a);
    }
  }
  cout << (1 == n ? 0 : max_flow(1, n)) << '\n';
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: ACCEPTED