Download Speed

#include <iostream>
#include <vector>
#include <limits.h>
#include <string.h>
#include <stack>

using namespace std;

class MaxFlow {
    int n;
    vector<vector<int>> capacity;
    vector<vector<int>> adj;

public:
    MaxFlow(int n) : n(n), capacity(n, vector<int>(n, 0)), adj(n) {}

    void addEdge(int u, int v, int cap) {
        capacity[u][v] += cap;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bool dfs(int source, int sink, vector<int>& parent) {
        vector<bool> visited(n, false);
        stack<int> s;
        s.push(source);
        visited[source] = true;

        while (!s.empty()) {
            int u = s.top();
            s.pop();

            for (int v : adj[u]) {
                if (!visited[v] && capacity[u][v] > 0) {
                    s.push(v);
                    visited[v] = true;
                    parent[v] = u;

                    if (v == sink) return true;
                }
            }
        }
        return false;
    }

    int fordFulkerson(int source, int sink) {
        int max_flow = 0;
        vector<int> parent(n);

        while (dfs(source, sink, parent)) {
            int path_flow = INT_MAX;
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                path_flow = min(path_flow, capacity[u][v]);
            }

            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                capacity[u][v] -= path_flow;
                capacity[v][u] += path_flow;
            }

            max_flow += path_flow;
        }
        return max_flow;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    MaxFlow maxFlow(n + 1);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        maxFlow.addEdge(a, b, c);
    }

    int result = maxFlow.fordFulkerson(1, n);
    cout << result << 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: ACCEPTED