Download Speed

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m;
vector<int> to;            
vector<ll> cap; 
vector<vector<int>> adj;   
vector<bool> vis;

ll dfs(int v, int t, ll flow, ll thold) {
    if (v == t) return flow;
    vis[v] = true;
    for (int e : adj[v]) {
        int u = to[e];
        if (!vis[u] && cap[e] >= thold) {
            ll r = dfs(u, t, min(flow, cap[e]), thold);
            if (r > 0) {
                cap[e] -= r;      
                cap[e ^ 1] += r; 
                return r;
            }
        }
    }
    return 0;
}

int main() {
    cin >> n >> m;
    if (n == 1) { 
        cout << 0 << endl; 
        return 0; 
    }
    adj.assign(n + 1, {});
    ll sum = 0;
    for (int i = 0; i < m; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        adj[a].push_back(to.size()); to.push_back(b); cap.push_back(c);
        adj[b].push_back(to.size()); to.push_back(a); cap.push_back(0);
        sum += c;
    }

    ll thold = 1;
    while (thold * 2 <= sum) thold *= 2; 

    ll flow = 0;
    while (thold >= 1) {
        while (true) {
            vis.assign(n + 1, false);
            ll f = dfs(1, n, LLONG_MAX, thold);
            if (f == 0) break;  
            flow += f;
        }
        thold /= 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