Download Speed

#include <bits/stdc++.h>
 
// using namespace std;
 
// #define debug(x) cerr << #x << ": " << x << endl;
// #define ll long long
// #define ull unsigned long long
// #define vi vector<int>
 
 
// #include <iostream>
// #include <vector>
// #include <queue>
// #include <cstring>
// #include <algorithm>
 
// using namespace std;
 
// struct Edge {
//     int to;
//     ull capacity;
//     ull flow; 
//     int rev;
// };
 
// class MaxFlow {
// public:
//     MaxFlow(int n) : n(n) {
//         adj.resize(n);
//     }
 
//     void add_edge(int u, int v, ull capacity) {
//         Edge a = {v, capacity, 0, (int)adj[v].size()};
//         Edge b = {u, 0       , 0, (int)adj[u].size()};
//         adj[u].push_back(a);
//         adj[v].push_back(b);
//     }
 
//     ull max_flow(int s, int t) {
//         ull total_flow = 0;
 
//         while (true) {
//             vector<int> parent(n, -1);
//             vector<int> edge_index(n, -1);
//             queue<int> q;
//             q.push(s);
//             parent[s] = s;
 
//             while (!q.empty() && parent[t] == -1) {
//                 int u = q.front();
//                 q.pop();
 
//                 for (int i = 0; i < (int) adj[u].size(); i++) {
//                     Edge &e = adj[u][i];
//                     if (parent[e.to] == -1 && e.capacity > e.flow) {
//                         parent[e.to] = u;
//                         edge_index[e.to] = i;
//                         q.push(e.to);
//                     }
//                 }
//             }
 
//             if (parent[t] == -1)
//                 break;
 
//             ull aug_flow = ULLONG_MAX;
//             for (int v = t; v != s; v = parent[v]) {
//                 int u = parent[v];
//                 int idx = edge_index[v];
//                 aug_flow = min(aug_flow, adj[u][idx].capacity - adj[u][idx].flow);
//             }
 
//             for (int v = t; v != s; v = parent[v]) {
//                 int u = parent[v];
//                 int idx = edge_index[v];
//                 adj[u][idx].flow += aug_flow;
//                 adj[v][adj[u][idx].rev].flow -= aug_flow;
//             }
 
//             total_flow += aug_flow;
//         }
 
//         return total_flow;
//     }
 
// private:
//     int n;
//     vector<vector<Edge>> adj;
// };
 
// int main() {
//     int n, m;
//     cin >> n >> m;
 
//     MaxFlow maxFlow(n);
//     int a, b; ull c;
//     for (int i = 0; i < m; i++) {
//         cin >> a >> b >> c; a--; b--;
//         maxFlow.add_edge(a, b, c);
//     }
 
//     cout << maxFlow.max_flow(0, n-1) << endl;
 
//     return 0;
// }
 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
 
using namespace std;
 
#define ull unsigned long long
 
class MaxFlow {
public:
    MaxFlow(int n) : n(n) {
        capacity.assign(n, vector<ull>(n, 0));  // Initialize capacity matrix with 0
    }
 
    // Add edge with capacity between nodes u and v
    void add_edge(int u, int v, ull cap) {
        capacity[u][v] += cap;  // Set the capacity of the edge from u to v
    }
 
    ull max_flow(int s, int t) {
        ull total_flow = 0;
 
        while (true) {
            // Perform BFS to find an augmenting path
            vector<int> parent(n, -1);  // To store the path (parent of each node)
            queue<pair<int, ull>> q;    // Queue for BFS
            q.push({s, ULLONG_MAX});
            parent[s] = s;  // Mark source as visited by assigning itself as parent
 
            while (!q.empty() && parent[t] == -1) {
                int u = q.front().first;
                ull flow = q.front().second;
                q.pop();
 
                for (int v = 0; v < n; v++) {
                    // If there's remaining capacity and v is not visited
                    if (parent[v] == -1 && capacity[u][v] > 0) {
                        parent[v] = u;
                        ull new_flow = min(flow, capacity[u][v]);
                        if (v == t) {
                            // If we reached the sink, update capacities along the path
                            total_flow += new_flow;
                            int cur = v;
                            while (cur != s) {
                                int prev = parent[cur];
                                capacity[prev][cur] -= new_flow;  // Reduce capacity along path
                                capacity[cur][prev] += new_flow;  // Add reverse flow (residual)
                                cur = prev;
                            }
                            goto next_iteration;  // Break out of the BFS loop and continue
                        }
                        q.push({v, new_flow});
                    }
                }
            }
 
            // If no augmenting path was found, we're done
            if (parent[t] == -1)
                break;
 
        next_iteration:;
        }
 
        return total_flow;
    }
 
private:
    int n;  // Number of nodes
    vector<vector<ull>> capacity;  // Capacity matrix
};
 
int main() {
    int n, m;
    cin >> n >> m;
 
    MaxFlow maxFlow(n);
    int a, b;
    ull c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;  // Input edge from a to b with capacity c
        a--; b--;  // 1-based to 0-based indexing
        maxFlow.add_edge(a, b, c);
    }
 
    cout << maxFlow.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: 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