Download Speed

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <limits>

using namespace std;

class Graph {
public:
    int n, m;
    vector<vector<long long>> capacity, flow;
    vector<vector<int>> adj;

    Graph(int n, int m) : n(n), m(m) {
        capacity.assign(n + 1, vector<long long>(n + 1, 0));
        flow.assign(n + 1, vector<long long>(n + 1, 0));
        adj.assign(n + 1, vector<int>());
    }

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

    int bfs(int source, int sink, vector<int>& parent) {
        vector<bool> visited(n + 1, 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] > flow[u][v]) {
                    visited[v] = true;
                    parent[v] = u;
                    if (v == sink)
                        return 1;
                    q.push(v);
                }
            }
        }
        return 0;
    }

    long long fordFulkerson(int source, int sink) {
        long long maxFlow = 0;
        vector<int> parent(n + 1);
        while (bfs(source, sink, parent)) {
            long long pathFlow = numeric_limits<long long>::max();
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                pathFlow = min(pathFlow, capacity[u][v] - flow[u][v]);
            }
            for (int v = sink; v != source; v = parent[v]) {
                int u = parent[v];
                flow[u][v] += pathFlow;
                flow[v][u] -= pathFlow;
            }
            maxFlow += pathFlow;
        }
        return maxFlow;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n, m);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        g.addEdge(a, b, c);
    }
    cout << g.fordFulkerson(1, 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