Download Speed

#include <bits/stdc++.h>

using namespace std;

const int N = 501;
vector<vector<pair<int, int>>> adj(N);
int vis[N];

int dfs(int n, int t, int w) {
    if(n == t) return w;
    
    vis[n] = 1;

    for(auto& [e, wn] : adj[n]) {
        if(!vis[e] && wn > 0) {
            int b = dfs(e, t, min(w, wn));
            if(b > 0) {
                wn -= b;
                for(auto& [node, cap] : adj[e]) {
                    if(node == n) {
                        cap += b;
                        break;
                    }
                }
                return b; 
            }
        }
    }

    return 0;
}

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

    for (int i = 0; i < m ; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, 0});
    }

    long long mf = 0;

    while(true) {
        memset(vis, 0, sizeof(vis));
        int f = dfs(1, n, INT_MAX);
        if(f == 0) break;
        mf += f;
    }

    cout << mf << '\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