Download Speed

#include <bits/stdc++.h>

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

static bool bfs(const int current, const int goal, const std::vector<std::vector<Edge>>& graph, std::vector<int>& parentVertex, std::vector<int>& parentEdge) {
    const size_t n = graph.size();
    parentVertex.assign(n, -1);
    parentEdge.assign(n, -1);

    parentVertex[current] = current;

    std::queue<int> q;
    q.push(current);
    while (!q.empty()) {
        const int v = q.front(); q.pop();

        for (int i = 0; i < static_cast<int>(graph[v].size()); i++) {
            const Edge& e = graph[v][i];

            if (e.cap > 0 && parentVertex[e.to] == -1) {
                parentVertex[e.to] = v;
                parentEdge[e.to] = i;
                q.push(e.to);

                if (e.to == goal) {
                    return true;
                }
            }
        }
    }

    return false;

}

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

    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<Edge>> graph(n + 1);
    while (m--) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        graph[a].emplace_back(b, c);
    }

    long long maxFlow = 0;

    std::vector<int> parentVertex, parentEdge;
    while (bfs(1, n, graph, parentVertex, parentEdge)) {
        long long pushed = std::numeric_limits<long long>::max();
        for (int v = n; v != 1; v = parentVertex[v]) {
            pushed = std::min(pushed, graph[parentVertex[v]][parentEdge[v]].cap);
        }

        for (int v = n; v != 1; v = parentVertex[v]) {
            graph[parentVertex[v]][parentEdge[v]].cap -= pushed;
        }

        maxFlow += pushed;
    }

    std::cout << maxFlow << std::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