Download Speed

input/code.cpp: In function 'uint64_t adjust_weights(std::vector<int>&, std::vector<std::vector<long unsigned int> >&)':
input/code.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 1; i < path.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
input/code.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 1; i < path.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <stack>
#include <functional>

std::vector<int> find_positive_path(int start, int end, std::vector<std::vector<int>> &edges, std::vector<std::vector<uint64_t>> &weights) {
    std::vector<bool> visited(edges.size(), false);

    std::function<std::vector<int>(int, int)> recurse = [&edges, &weights, &visited, &recurse](int start, int end) -> std::vector<int> {
        if (start == end) return {end};
        
        visited[start] = true;
        std::vector<int> path;
        path.push_back(start);
        //std::cout << "Adding " << start+1 << std::endl;
        for (auto &edge : edges[start]) {
            if (visited[edge]) continue;
            if (weights[start][edge] == 0) continue;
            
            //std::cout << "Checking edge " << start+1 << " " << edge+1 << std::endl;
            std::vector<int> rescursed_path = recurse(edge, end);
            if (rescursed_path.size() > 0) {
                path.insert(path.end(), rescursed_path.begin(), rescursed_path.end());
                break;
            }
            //std::cout << "No valid path with " << edge+1 << std::endl;
        }

        if (path.size() == 1) {
            //std::cout << "Removing " << start+1 << std::endl;
            visited[start] = false;
            return {};
        };
        //std::cout << "Found path" << std::endl;
        return path;
    };

    return recurse(start, end);
}

uint64_t adjust_weights(std::vector<int> &path, std::vector<std::vector<uint64_t>> &weights) {
    //std::cout << "Adjusting Path: ";
    uint64_t min_weight = UINT64_MAX;
    for (int i = 1; i < path.size(); ++i) {
        min_weight = std::min(min_weight, weights[path[i-1]][path[i]]);
        //std::cout << path[i-1]+1 << " ";
    }
    //std::cout << path[path.size()-1]+1 << std::endl;
    //std::cout << "minimum weight: " << min_weight << std::endl;

    for (int i = 1; i < path.size(); ++i) {
        weights[path[i-1]][path[i]] -= min_weight;
        weights[path[i]][path[i-1]] += min_weight;
    }
    return min_weight;
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> edges(n);
    std::vector<std::vector<uint64_t>> weights(n, std::vector<uint64_t>(n, 0));
    for (int i = 0; i < m; ++i) {
        int a, b;
        uint64_t c;
        std::cin >> a >> b >> c;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
        weights[a-1][b-1] += c;
    }

    bool is_max_flow = false;
    uint64_t max_flow = 0;
    while(!is_max_flow) {
        std::vector<int> path = find_positive_path(0, n-1, edges, weights);
        if (path.size() == 0) {
            is_max_flow = true;
            continue;
        }

        max_flow += adjust_weights(path, weights);
    }

    std::cout << max_flow << std::endl;
}

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: TIME LIMIT EXCEEDED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED