Download Speed

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll adj[501][501];
ll ff[501][501];
ll bf[501][501];
ll path[501];
bool visited[501];
ll pidx;

bool dfs(ll s, ll e, ll n){
    path[pidx++] = s;
    visited[s] = true;
    if(s == e){
        return true;
    }
    for(ll i=1; i<=n; i++){
        if(ff[s][i]>0 && !visited[i]){
            if(dfs(i, e, n)){
                return true;
            }
        }
        // if(bf[i][s]>0 && !visited[i]){
        //     if(dfs(i, e, n)){
        //         return true;
        //     }
        // }
    }
    pidx--;
    return false;
}

bool findpath(ll s, ll e, ll n){
    pidx=0;
    memset(visited, 0, n+1);
    return dfs(s, e, n);
}

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

    for(ull i=0; i<m; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a][b] += c;
        // adj[a][b] = c;
        ff[a][b] += c;
        bf[a][b] = 0;
    }

    ll s = 0;
    while(findpath(1, n, n)){
        ll m = LLONG_MAX;
        for(ll i=1; i<pidx; i++){
            m = min(m, ff[path[i-1]][path[i]]);
        }
        for(ll i=1; i<pidx; i++){
            ff[path[i-1]][path[i]] -= m;
            ff[path[i]][path[i-1]] += m;
            // bf[path[i-1]][path[i]] += m;
        }
        s += m;
    }

    // ll s = 0;
    // for(ull i=1; i<=n; i++){
    //     if(adj[i][n]){
    //         s += ff[i][n];
    //     }
    // }
    cout << s << 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