Internet connection

#include <algorithm>
#include <cstdint>
#include <deque>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::deque;
using std::endl;
using std::make_pair;
using std::min;
using std::pair;
using std::vector;


#define MAX_FLOW 1000000000


pair<uint32_t, vector<size_t>> find_path(
        const size_t n, const vector<vector<uint32_t>> weights,
        const size_t start, const size_t finish) {
    vector<size_t> visited(n + 1, 0);
    visited[start] = start;

    deque<size_t> next;
    next.push_back(start);

    while (next.size() > 0 && next.front() != finish) {
        const size_t current = next.front();
        next.pop_front();

        for (size_t j = 1; j <= n; j++) {
            if (visited[j] == 0 && weights[current - 1][j - 1]) {
                visited[j] = current;
                next.push_back(j);
            }
        }
    }

    vector<size_t> path;
    uint32_t max_flow = MAX_FLOW + 1;

    for (
            size_t current = finish;
            current != 0 && current != start;
            current = visited[current]
        ) {

        const size_t next = visited[current];

        if (next != current && next != 0) {
            max_flow = min(max_flow, weights[next - 1][current - 1]);
            path.push_back(current);
        }
    }

    path = vector<size_t>(path.rbegin(), path.rend());

    return make_pair(max_flow % (MAX_FLOW + 1), path);
}


int main() {
    size_t n;
    size_t m;
    cin >> n >> m;

    const size_t start = 1;
    const size_t finish = n;

    vector<vector<uint32_t>> weights(n, vector<uint32_t>(n, 0));

    for (size_t i = 0; i < m; i++) {
        size_t a;
        size_t b;
        uint32_t c;
        cin >> a >> b >> c;

        weights[a - 1][b - 1] = c;
    }

    uint64_t flow = 0;

    while (true) {
        const auto result = find_path(n, weights, start, finish);
        const uint32_t current_flow = result.first;
        const vector<size_t> path = result.second;

        if (current_flow == 0) {
            break;
        }

        flow += current_flow;

        size_t previous = start;
        for (auto i : path) {
            weights[previous - 1][i - 1] -= current_flow;
            weights[i - 1][previous - 1] += current_flow;

            previous = i;
        }
    }

    cout << flow << 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