Download Speed

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
 
using namespace std;
 
typedef long long ll;
 
struct Edge {
    int to, rev;
    ll cap, flow;
};
 
class MaxFlow {
public:
    MaxFlow(int n) : n(n), graph(n), level(n), ptr(n) {}
 
    void addEdge(int s, int t, ll cap) {
        Edge a = {t, (int)graph[t].size(), cap, 0};
        Edge b = {s, (int)graph[s].size(), 0, 0};  // Reverse edge with 0 capacity
        graph[s].push_back(a);
        graph[t].push_back(b);
    }
 
    ll dinic(int s, int t) {
        ll maxFlow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (ll pushed = dfs(s, t, INF))
                maxFlow += pushed;
        }
        return maxFlow;
    }
 
private:
    const ll INF = numeric_limits<ll>::max();
    int n;
    vector<vector<Edge>> graph;
    vector<int> level, ptr;
 
    bool bfs(int s, int t) {
        level.assign(n, -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty() && level[t] == -1) {
            int v = q.front(); q.pop();
            for (Edge &e : graph[v]) {
                if (level[e.to] == -1 && e.flow < e.cap) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }
 
    ll dfs(int v, int t, ll flow) {
        if (flow == 0) return 0;
        if (v == t) return flow;
        for (int &cid = ptr[v]; cid < (int)graph[v].size(); cid++) {
            Edge &e = graph[v][cid];
            if (level[e.to] != level[v] + 1 || e.flow >= e.cap)
                continue;
            ll pushed = dfs(e.to, t, min(flow, e.cap - e.flow));
            if (pushed) {
                e.flow += pushed;
                graph[e.to][e.rev].flow -= pushed;
                return pushed;
            }
        }
        return 0;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
    MaxFlow mf(n);
 
    for (int i = 0; i < m; ++i) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        --a; --b;  // Zero-based indexing
        mf.addEdge(a, b, c);
    }
 
    ll maxFlow = mf.dinic(0, n - 1);
    cout << maxFlow << '\n';
 
    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: ACCEPTED