Download Speed

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

typedef long long ll;

const ll N = 501;

vector<ll> adj[N];
ll weights[N][N] = {0};

ll min_weight = 0;


bool dfs(ll s, vector<ll>& visited, ll target, ll tresh, ll parents[]) {
    if (visited[s] == 1) return false;
    
    visited[s] = 1;
    //cout << "loop1";
    for (auto u: adj[s]) {
        //cout << "loop2";
        ll c = weights[s][u];
        //cout << "weight found = " << c << endl;
        if(c >= tresh && c > 0) {
            if(target == u) {
                parents[u] = s;
                min_weight = c;
                return true;
            }
            if(dfs(u, visited, target, tresh, parents)) {
                min_weight = min(min_weight, c);
                parents[u] = s;
                return true;    
            }
        }
    }
    return false;
}

void update_weight(ll parents[], ll n) {
    ll p = n;
    while(p != 1) {
        weights[p][parents[p]] += min_weight;
        weights[parents[p]][p] -= min_weight;
        p = parents[p];
    }
}

int main() {
    ll n, m;
    cin >> n >> m;

    vector<ll> visited(n+1, 0);


    ll a,b,c;
    ll tresh = 0;
    bool original[n+1][n+1] = {false};
    for(ll i = 0; i<m; i++) {
        cin >> a >> b >> c;
        tresh += c;
        adj[a].push_back(b);
        adj[b].push_back(a);
        weights[a][b] += c;
        original[a][b] = true;
    }

    ll parents[n+1] = {0};
    ll out = 0;
    //cout << "thresh = " << tresh << endl;
    while(tresh > 0) {
        fill(visited.begin(), visited.end(), 0);
        if(dfs(1, visited, n, tresh, parents)) {
            //cout << "One path found" << endl;
            out += min_weight;
            update_weight(parents, n);
            
        } else {
            tresh /= 2;
            //cout << "thresh = " << tresh << endl;
        }
    }

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