Download Speed

#include <iostream>
#include <vector>
#include <limits.h>
#include <queue>

using namespace std;

class MaxFlow {
    int n; // Number of vertices
    vector<vector<int>> capacity; // Capacity graph
    vector<vector<int>> adj; // Adjacency list

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; // Add capacity to the edge
        adj[u].push_back(v); // Add to adjacency list
        adj[v].push_back(u); // Add reverse edge to adjacency list
    }

    bool bfs(int source, int sink, vector<int>& parent) {
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(source);
        visited[source] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

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

                    if (v == sink) return true; // Reached the sink
                }
            }
        }
        return false; // No more augmenting path
    }

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

        while (bfs(source, sink, parent)) {
            // Find the maximum flow through the path found.
            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]);
            }

            // Update capacities of the edges and reverse edges along the path
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                capacity[u][v] -= path_flow; // Update forward edge
                capacity[v][u] += path_flow; // Update reverse edge
            }

            max_flow += path_flow; // Add path flow to overall flow
        }
        return max_flow;
    }
};

int main() {
    int n, m;
    cin >> n >> m; // Read number of vertices and edges
    MaxFlow maxFlow(n + 1); // n + 1 since nodes are 1-indexed

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

    cout << maxFlow.fordFulkerson(1, n) << endl; // Output the maximum flow from node 1 to node n
    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