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