Download Speed

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

using namespace std;
typedef long long ll;

ll MAX_C = 1000000000;
int n, m;
struct Edge {
    int to;
    ll cost;
};
vector<Edge> edges;
vector<vector<int>> adj;
vector<char> vis;

void add_edge(int a, int b, ll cost) {
    adj[a].push_back(edges.size());
    edges.push_back({b, cost});
    adj[b].push_back(edges.size());
    edges.push_back({a, 0});
}

ll dfs(int node, ll threshold, ll flow) {

    if (node == n)
        return flow;

    vis[node] = 1;

    for (int e : adj[node]) {
        Edge &edge = edges[e];

        if (edge.cost < threshold || vis[edge.to])
            continue;

        ll val = dfs(edge.to, threshold, min(flow, edge.cost));
        if (val > 0) {
            edge.cost -= val;
            edges[e ^ 1].cost += val;
            return val;
        }
    }
    return 0;
}

ll find() {
    int t = MAX_C;
    int val = dfs(1, t, t);
    while (val == 0 && t > 0) {
        fill(vis.begin(), vis.end(), 0);
        t /= 2;
        val = dfs(1, t, MAX_C);
    }
    return val;
}

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

    cin >> n >> m;
    adj = vector<vector<int>>(n + 1);
    vis.assign(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        ll cost;
        cin >> a >> b >> cost;
        add_edge(a, b, cost);
    }

    ll flow = -1;
    ll val = 1;

    while (val > 0) {
        flow += val;
        val = find();
    }

    cout << flow << "\n";
    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: ACCEPTED