Download Speed

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    long long cap;
};

void add_edge(int a, int b, long long c, vector<Edge>& edges, vector<vector<int>>& adj) {
    adj[a].push_back(edges.size());
    edges.push_back({b, c});
    adj[b].push_back(edges.size());
    edges.push_back({a, 0});
}

bool bfs(int s, int t, const vector<Edge>& edges, const vector<vector<int>>& adj, vector<int>& level) {
    fill(level.begin(), level.end(), -1);
    level[s] = 0;

    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int id : adj[v]) {
            const Edge& e = edges[id];
            if (e.cap > 0 && level[e.to] == -1) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
    return level[t] != -1;
}

long long dfs(int v, int t, long long pushed, vector<Edge>& edges, const vector<vector<int>>& adj,
              const vector<int>& level, vector<int>& ptr) {
    if (v == t) {
        return pushed;
    }

    for (; ptr[v] < (int)adj[v].size(); ptr[v]++) {
        int id = adj[v][ptr[v]];
        Edge& e = edges[id];
        if (e.cap > 0 && level[e.to] == level[v] + 1) {
            long long got = dfs(e.to, t, min(pushed, e.cap), edges, adj, level, ptr);
            if (got > 0) {
                e.cap -= got;
                edges[id ^ 1].cap += got;
                return got;
            }
        }
    }
    return 0;
}

long long max_flow(int s, int t, int n, vector<Edge>& edges, const vector<vector<int>>& adj) {
    if (s == t) {
        return 0;
    }

    vector<int> level(n + 1), ptr(n + 1);
    long long flow = 0;

    while (bfs(s, t, edges, adj, level)) {
        fill(ptr.begin(), ptr.end(), 0);
        while (long long pushed = dfs(s, t, LLONG_MAX, edges, adj, level, ptr)) {
            flow += pushed;
        }
    }
    return flow;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<Edge> edges;
    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        add_edge(a, b, c, edges, adj);
    }

    cout << max_flow(1, n, n, edges, adj) << "\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