Download Speed

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>


const int N = 501;
std::vector<int> adj[N];
long long capPerCheckpoint[N];

long long dfsWithFlow(int u, long long flow, int t, bool visited[N], long long capacity[N][N]) {
  if (u == t) return flow;
  visited[u] = true;

  for (int v : adj[u]) {
    if (!visited[v] && capacity[u][v] > 0) {
      long long pushed = dfsWithFlow(v, std::min(flow, capacity[u][v]), t, visited, capacity);
      if (pushed > 0) {
        capacity[u][v] -= pushed;
        capacity[v][u] += pushed;
        return pushed;
      }
    }
  }
  return 0; // no flow
}

long long maxflow(int s, int t, long long capacity[N][N]) {
  long long flow = 0;
  
  // push till no augmenting path is availabl
  while (true) {
    bool visited[N] = {false};
    long long pushed = dfsWithFlow(s, std::numeric_limits<long long>::max(), t, visited, capacity);
    if (pushed == 0) break; 
    flow += pushed;
  }

  return flow;
}

int main() {
  int n, m;
  std::cin >> n >> m;

  int s = 1;
  int t = n;

  long long capacity[N][N] = {{0}};


  for (int i = 0; i < m; ++i) {
    int a, b;
    long long c;
    std::cin >> a >> b >> c;
    adj[a].push_back(b);
    adj[b].push_back(a); //residual graph
    capacity[a][b] += c;
  }

  long long f = maxflow(s, t, capacity);
  std::cout << f << "\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