Download Speed

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

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

std::vector<Edge> edges;
std::vector<std::vector<int>> adj;
std::vector<bool> visited;

long long dfs(int v, int n, long long f, long long delta) {
    if (v == n) return f;
    visited[v] = true;
    for (int id : adj[v]) {
        int to = edges[id].to;
        if (!visited[to] && edges[id].cap >= delta) {
            long long pushed = dfs(to, n, std::min(f, edges[id].cap), delta);
            if (pushed > 0) {
                edges[id].cap -= pushed;
                edges[id ^ 1].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n, m;
    std::cin >> n >> m;
    adj.resize(n + 1);
    visited.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        edges.push_back({b, c});
        adj[a].push_back(edges.size() - 1);
        edges.push_back({a, 0});
        adj[b].push_back(edges.size() - 1);
    }
    long long flow = 0;
    const long long INF = 4e18;
    for (long long delta = 1 << 30; delta > 0; delta /= 2) {
        while (true) {
            std::fill(visited.begin(), visited.end(), false);
            long long pushed = dfs(1, n, INF, delta);
            if (pushed == 0) break;
            flow += pushed;
        }
    }
    std::cout << flow << '\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