Download Speed

#include <bits/stdc++.h>

using namespace std;

struct Flow {

    int n;
    vector<vector<int>> *capacity;
    vector<vector<int>> *adj;

    Flow(vector<vector<int>> &adj, vector<vector<int>> &capacity) {
        n = adj.size();
        this->adj = &adj;
        this->capacity = &capacity;
    }

    int bfs(int s, int t, vector<int>& parent) {
        fill(parent.begin(), parent.end(), -1);
        parent[s] = -2;
        queue<pair<int, int>> q;
        q.push({s, INT_MAX});

        while (!q.empty()) {
            int current = q.front().first;
            int flow = q.front().second;
            q.pop();

            for (int next : (*adj)[current]) {
                if (parent[next] == -1 && (*capacity)[current][next] > 0) {
                    parent[next] = current;
                    int new_flow = min(flow, (*capacity)[current][next]);
                    if (next == t)
                        return new_flow;
                    q.push({next, new_flow});
                }
            }
        }

        return 0;
    }

    int max_flow(int s, int t) {
        vector<int> parent(n);
        int flow = 0;
        int new_flow;

        while ((new_flow = bfs(s, t, parent))) {
            flow += new_flow;
            int current = t;
            while (current != s) {
                int previous = parent[current];
                (*capacity)[previous][current] -= new_flow;
                (*capacity)[current][previous] += new_flow;
                current = previous;
            }
        }

        return flow;
    }

};

int main() {

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n);
    vector<vector<int>> capacity(n, vector<int>(n, 0));

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

    Flow flow{adj, capacity};

    cout << flow.max_flow(0, n-1) << endl;

    return 0;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER