Download Speed

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

using ll = long long;

int n, m;
vector<int> to;
vector<ll> cap;
vector<vector<int>> adj;

void addEdge(int a, int b, ll c){
  adj[a].push_back(to.size());  
  to.push_back(b);
  cap.push_back(c);

  adj[b].push_back(to.size());   
  to.push_back(a);
  cap.push_back(0);
}

ll bfs(){
  vector<int> parentEdge(n + 1, -1);
  vector<bool> vis(n + 1, false);
  queue<int> q;
  q.push(1);
  vis[1] = true;

  while(!q.empty() && !vis[n]){
    int v = q.front(); q.pop();
    for(int e : adj[v]){
      if(cap[e] > 0 && !vis[to[e]]){
        vis[to[e]] = true;
        parentEdge[to[e]] = e;
        q.push(to[e]);
      }
    }
  }

  if(!vis[n]) return 0;

  ll f = (ll)1e18;
  for(int v = n; v != 1; v = to[parentEdge[v] ^ 1])
    f = min(f, cap[parentEdge[v]]);

  for(int v = n; v != 1; v = to[parentEdge[v] ^ 1]){
    int e = parentEdge[v];
    cap[e] -= f;
    cap[e ^ 1] += f;
  }

  return f;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m;
  adj.assign(n + 1, {});

  for(int i = 0; i < m; ++i){
    int a, b;
    ll c;
    cin >> a >> b >> c;
    addEdge(a, b, c);
  }

  ll flow = 0, f;
  while((f = bfs()) > 0) flow += f;

  cout << flow << endl;
}

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