Download Speed

#include <bits/stdc++.h>
 
using namespace std;
 
#define debug(x) cerr << #x << ": " << x << endl;
#define ll long long
#define ull unsigned long long
#define vi vector<int>
 
 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
struct Edge {
    int to;
    ull capacity;
    ull flow; 
    int rev;
};
 
class MaxFlow {
public:
    MaxFlow(int n) : n(n) {
        adj.resize(n);
    }
 
    void add_edge(int u, int v, ull capacity) {
        Edge a = {v, capacity, 0, (int)adj[v].size()};
        Edge b = {u, 0       , 0, (int)adj[u].size()};
        adj[u].push_back(a);
        adj[v].push_back(b);
    }
 
    ull max_flow(int s, int t) {
        ull total_flow = 0;
 
        while (true) {
            vector<int> parent(n, -1);
            vector<int> edge_index(n, -1);
            queue<int> q;
            q.push(s);
            parent[s] = s;
 
            while (!q.empty() && parent[t] == -1) {
                int u = q.front();
                q.pop();
 
                for (int i = 0; i < (int) adj[u].size(); i++) {
                    Edge &e = adj[u][i];
                    if (parent[e.to] == -1 && e.capacity > e.flow) {
                        parent[e.to] = u;
                        edge_index[e.to] = i;
                        q.push(e.to);
                    }
                }
            }
 
            if (parent[t] == -1)
                break;
 
            ull aug_flow = ULLONG_MAX;
            for (int v = t; v != s; v = parent[v]) {
                int u = parent[v];
                int idx = edge_index[v];
                aug_flow = min(aug_flow, adj[u][idx].capacity - adj[u][idx].flow);
            }
 
            for (int v = t; v != s; v = parent[v]) {
                int u = parent[v];
                int idx = edge_index[v];
                adj[u][idx].flow += aug_flow;
                adj[v][adj[u][idx].rev].flow -= aug_flow;
            }
 
            total_flow += aug_flow;
        }
 
        return total_flow;
    }
 
private:
    int n;
    vector<vector<Edge>> adj;
};
 
int main() {
    int n, m;
    cin >> n >> m;
 
    MaxFlow maxFlow(n);
    int a, b; ull c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c; a--; b--;
        maxFlow.add_edge(a, b, c);
    }
 
    cout << maxFlow.max_flow(0, n-1) << endl;
 
    return 0;
}

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: WRONG ANSWER