Download Speed

#include <iostream>
#include <vector>
#include <cmath>
#include <bits/stdc++.h>

using namespace std;

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

bool dfsRec(vector<vector<Edge>> & graph,
            vector<int> &visited, int s, vector<Edge*> & res,
            long long weight_threshold, long long & min_weight) {
    int end_node = graph.size() - 1;
    if (s == end_node) return true;

    visited[s] = 1;

    for (Edge & edge : graph[s])
    {
        if (visited[edge.to] == 0 && edge.cap >= weight_threshold)
        {
            if (dfsRec(graph, visited, edge.to, res, weight_threshold, min_weight))
            {
                res.push_back(&edge);
                min_weight = min(min_weight, edge.cap);
                return true;
            }
        }
    }
    return false;
}

vector<Edge*> dfs(vector<vector<Edge>> & graph, long long weight_threshold, long long & min_weight) {
    vector<int> visited(graph.size(), 0);
    vector<Edge*> res;
    min_weight = LONG_LONG_MAX;

    bool found = dfsRec(graph, visited, 1, res, weight_threshold, min_weight);

    if (!found) return {};
    return res;
}


int main()
{
    long long n_computers;
    long long n_connections;
    cin >> n_computers >> n_connections;

    vector<vector<Edge>> graph(n_computers + 1);
    for (int i = 0; i < n_connections; ++i)
    {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c, (int)graph[b].size()});
        graph[b].push_back({a, 0, (int)graph[a].size() - 1});
    }

    long long threshold = 1LL << 30;
    long long flow = 0;
    long long min_weight = 0;
    while (threshold > 0)
    {
        vector<Edge*> res = dfs(graph, threshold, min_weight);
        if (!res.empty())
        {
            flow += min_weight;
            for (Edge* e : res)
            {
                e->cap -= min_weight;
                graph[e->to][e->rev].cap += min_weight;
            }
        }
        else
        {
            threshold /= 2;
        }
    }
    cout << flow << 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: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED