⚙️AlgorithmIntermediate

Maximum Flow - Ford-Fulkerson

Key Points

•
Ford–Fulkerson finds the maximum possible flow from a source to a sink by repeatedly pushing flow along an augmenting path in the residual graph.
•
The residual graph tracks how much more flow can go forward and how much already-sent flow can be sent back to reroute if needed.
•
An augmenting path increases total flow by the path’s bottleneck capacity, and we repeat until no such path exists.
•
If capacities are integers, basic Ford–Fulkerson with DFS runs in O(E · F) time, where F is the max-flow value.
•
Edmonds–Karp is the BFS variant that guarantees O(V · $E^{2}$ ) time by always choosing the shortest (in edges) augmenting path.
•
Capacity scaling improves performance when capacities are large by only searching edges with capacity at least a threshold that halves each phase.
•
After computing max flow, the reachable set in the residual graph gives a minimum s–t cut by the Max-Flow Min-Cut Theorem.
•
Use long long and always add reverse edges to avoid overflow and correctness bugs in C++ implementations.

Prerequisites

→Graphs and adjacency lists — Max-flow algorithms operate on directed graphs and require efficient edge storage.
→Breadth-first search (BFS) and depth-first search (DFS) — Ford–Fulkerson uses path searches; Edmonds–Karp specifically relies on BFS.
→Big-O notation and asymptotic analysis — Understanding performance guarantees and trade-offs requires analyzing O(V·E^2) vs O(E·F), etc.
→Basic C++ data structures (vectors, queues) — Implementing residual graphs and BFS/DFS efficiently depends on these containers.
→Mathematical reasoning with sums and minima — Residual capacities, bottlenecks, and cuts use simple but precise definitions and proofs.

Detailed Explanation

Tap terms for definitions

01Overview

Maximum flow is about pushing as much “stuff” as possible from a source node to a sink node through a directed network with capacities on edges. The Ford–Fulkerson method is a simple and powerful approach: as long as there exists a path from source to sink where every edge still has remaining capacity, we can increase the flow by the smallest remaining capacity along that path (the bottleneck). To support this, we maintain a residual graph: forward edges show how much more we can push; reverse edges show how much of the current flow we can cancel to reroute it. Repeating this process eventually reaches an optimal flow, proven by the Max-Flow Min-Cut Theorem. Different ways of finding augmenting paths give different running times: depth-first search (DFS) is often fast in practice but has only a weak theoretical bound dependent on the max-flow value, while breadth-first search (BFS) in Edmonds–Karp guarantees polynomial time. Capacity scaling further improves performance when capacities are large by focusing on “big” edges first. Max flow underlies many problems such as bipartite matching, disjoint paths, scheduling with capacity constraints, and minimum cuts in images and graphs.

02Intuition & Analogies

Imagine a city’s water network: a reservoir (source) must deliver as much water as possible to a treatment plant (sink) through pipes (directed edges) that each have a maximum safe flow (capacity). Initially, no water flows. You look for a route of pipes from the reservoir to the plant such that each pipe still has spare room; send as much as the tightest pipe on that route allows. That tightest pipe is the bottleneck. Do this again and again. Sometimes, after sending water along one set of routes, you realize you could do better by partially undoing (sending water back) through some pipes and redirecting along a new, more efficient route. The “ability to send back” is modeled by reverse edges in the residual graph—like adjustable valves that can reclaim already-used capacity to improve the overall plan. Using DFS to find routes is like exploring one tunnel deeply; using BFS (Edmonds–Karp) is like always choosing the route with the fewest pipe segments, which tends to avoid wasting effort on long detours. Capacity scaling is like first installing major water mains (big-capacity routes) before fiddling with small garden hoses, which speeds up getting most of the water through quickly. When you can’t find any route with spare capacity, you’ve implicitly identified a choke boundary (a cut) whose total pipe capacity equals the total water delivered, guaranteeing optimality.

03Formal Definition

A flow network is a directed graph G = (V, E) with a capacity function c: E →

R_{\geq 0}

, a source s ∈ V, and a sink t ∈ V. A flow is a function f: V ×

V \to R

satisfying: (1) Capacity constraints: 0 ≤ f(u, v) ≤ c(u, v) for all (u, v) ∈ E and f(u, v) = 0 if (u, v) ∉ E. (2) Skew symmetry: f(u, v) = −f(v, u). (3) Flow conservation: for all u ∈ V \ {s, t},

\sum_{v \in V}

f(u, v) = 0. The value of a flow is

∣ f ∣

\sum_{v \in V}

f(s, v), the net outflow from the source. The residual capacity with respect to f is r(u, v) = c(u, v) − f(u, v) for forward edges and r(v, u) = f(u, v) for reverse edges. The residual graph

G_{f}

contains all edges (u, v) with r(u, v) > 0. An augmenting path is an s–t path in

G_{f}

. Given an augmenting path P and bottleneck Δ =

mi n_{(u, v) \in P}

r(u, v), we produce a new flow f' by increasing f on forward edges of P by Δ and decreasing on reverse edges by Δ. Ford–Fulkerson repeats augmentation until no augmenting path exists; by the Max-Flow Min-Cut Theorem, the resulting flow is maximum and equals the capacity of some minimum s–t cut.

04When to Use

Use Ford–Fulkerson and its variants whenever you must route as much as possible through a capacity-limited network. Common applications include: (1) Bipartite matching (convert to a flow network; maximum matching equals max flow). (2) Edge- or vertex-disjoint paths (ensure each edge or vertex has unit capacity). (3) Scheduling with resource limits (time slots as edges with capacities). (4) Project selection and minimum cut formulations (separate profitable and unprofitable choices with constraints). (5) Image segmentation and graph cuts (min s–t cut yields foreground/background separation). For contest problems: (a) If graphs are modest (e.g., up to a few thousand edges) and capacities are small integers, DFS-based Ford–Fulkerson often passes. (b) For safer polynomial guarantees, use Edmonds–Karp (BFS). (c) If capacities vary widely or are large, capacity scaling can be significantly faster in practice. If graphs are large and dense or extremely performance-sensitive, consider Dinic’s algorithm—but understanding Ford–Fulkerson first is essential.

⚠️Common Mistakes

Forgetting reverse edges: Without adding a reverse edge of initial capacity 0 for every forward edge, you cannot cancel and reroute flow, breaking correctness. Always store forward and reverse edges with cross indices. - Using 32-bit int for capacities/flow: Sums can overflow. Prefer long long (64-bit) in C++. - Not resetting visited arrays per augmentation: DFS/BFS must consider a fresh search each iteration; otherwise, you may miss valid paths. - Ignoring parallel edges: Combine or store both; if you overwrite one with another, capacity is lost. - Mishandling 0-capacity edges: Keep them but they should not be traversed in residual searches (cap > 0 checks). - Mixing 0-based and 1-based node indices: Standardize input handling and document it. - Recursion depth: Deep DFS on large graphs can overflow the stack; consider iterative DFS/BFS or increase stack if necessary. - Forgetting to record original capacities when you need to output a min cut: Residual capacities change; keep a separate list for reporting the cut. - Termination with non-integer capacities: The basic DFS strategy’s O(E·F) bound assumes integer capacities; with irrationals, careless implementations may cycle. Use BFS (Edmonds–Karp) or rational/integer capacities for guarantees.

Key Formulas

Capacity constraint

0 \leq f (u, v) \leq c (u, v)

Explanation: Flow on any edge cannot exceed its capacity and cannot be negative. This ensures physical limits are respected.

Skew symmetry

f (u, v) = - f (v, u)

Explanation: Sending x units from u to v is equivalent to sending −x from v to u. This makes reverse edges naturally represent cancellation.

Flow conservation

v \in V \sum f (u, v) = 0 for u \neq = s, t

Explanation: Every intermediate node forwards exactly what it receives. Only the source emits and the sink absorbs net flow.

Value of a flow

∣ f ∣ = v \in V \sum f (s, v) = v \in V \sum f (v, t)

Explanation: The total flow is the net outflow from the source, which also equals the net inflow to the sink. It measures how much is delivered.

Residual capacity

r (u, v) = c (u, v) - f (u, v), r (v, u) = f (u, v)

Explanation: Forward residual is unused capacity; backward residual is how much you can cancel. Residual edges define where more flow can go.

Bottleneck on a path

Δ = (u, v) \in P min r (u, v)

Explanation: The maximum extra flow we can push along an augmenting path P equals the smallest residual capacity on that path.

Augmentation update

f^{'} (u, v) = f (u, v) + Δ \cdot χ_{(u, v) \in P} - Δ \cdot χ_{(v, u) \in P}

Explanation: Increase flow by Δ on forward edges of P and decrease by Δ on reverse edges. This preserves feasibility and increases total flow by Δ.

Cut capacity

c (S, T) = u \in S \sum v \in T \sum c (u, v)

Explanation: The capacity of cut (S,T) sums capacities of edges leaving S. This bounds any s–t flow from above.

Max-Flow Min-Cut Theorem

max ∣ f ∣ = min c (S, T)

Explanation: The maximum achievable flow equals the minimum cut capacity. When no augmenting path exists, you have reached this equality.

Ford–Fulkerson (DFS) time

T_{FF-DFS} = O (E \cdot F)

Explanation: With integer capacities, each augmentation increases flow by at least 1, and each augmentation costs O(E) to find and update, totaling O(E·F).

Edmonds–Karp time

T_{EK} = O (V \cdot E^{2})

Explanation: Each BFS-based augmentation is O(E), and the number of augmentations is O(V·E) because the shortest-path distance to t increases at most O(V·E) times.

Capacity scaling time

T_{Scaling} = O (E^{2} lo g U)

Explanation: Restricting searches to edges with residual ≥ $Δ$ and halving $Δ$ each phase yields O( $E^{2}$ ) work per phase times O( $lo g$ U) phases, where U is the max capacity.

Complexity Analysis

Let n =

∣ V ∣

and m =

∣ E ∣

. In Ford–Fulkerson with a generic augmenting-path search (often implemented with DFS), each augmentation requires O(m) time to find a path and update residual capacities. If all capacities are integers, the flow value strictly increases by at least 1 each augmentation, so the number of augmentations is at most F, the maximum flow value. This yields O(m · F) time, which can be fast when F is small but poor when F is large; it also lacks a polynomial guarantee if capacities are large or irrational. Edmonds–Karp replaces DFS with BFS to find the shortest augmenting path in terms of edges. Each augmentation and update still costs O(m), but a key lemma shows the distance from s to any vertex in the residual graph never decreases, and edges can become critical only O(n) times before their residual distance increases. This bounds the number of augmentations by O(n · m), giving a total time of O(n ·

m^{2}

). Capacity scaling improves behavior when capacities vary widely: by ignoring edges below a threshold

Δ

that halves each phase, you reduce the number of ineffective small pushes. Using BFS within scaling yields O(

m^{2}

log U), where U is the maximum capacity on any edge. Space usage for all variants is O(n + m), storing adjacency lists and reverse edges. Practical performance depends strongly on graph structure: sparse graphs and small F favor DFS; large F or adversarial graphs favor Edmonds–Karp or scaling. After computing max flow, extracting a min cut is a single O(n + m) traversal of the residual graph from s.

Code Examples

Ford–Fulkerson with DFS (basic residual graph)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge {
5     int to;            // destination vertex
6     long long cap;     // residual capacity on this edge
7     int rev;           // index of the reverse edge in g[to]
8 };
9 
10 struct MaxFlowDFS {
11     int n;
12     vector<vector<Edge>> g; // residual graph
13 
14     MaxFlowDFS(int n): n(n), g(n) {}
15 
16     void add_edge(int u, int v, long long c) {
17         // forward edge u->v with capacity c
18         Edge a{v, c, (int)g[v].size()};
19         // reverse edge v->u with initial 0 capacity
20         Edge b{u, 0, (int)g[u].size()};
21         g[u].push_back(a);
22         g[v].push_back(b);
23     }
24 
25     long long dfs(int v, int t, long long f, vector<int>& vis) {
26         if (v == t) return f;        // reached sink, can push f
27         vis[v] = 1;
28         for (auto &e : g[v]) {
29             if (!vis[e.to] && e.cap > 0) {
30                 long long pushed = dfs(e.to, t, min(f, e.cap), vis);
31                 if (pushed > 0) {
32                     // use residual capacities to update
33                     e.cap -= pushed;                          // reduce forward residual
34                     g[e.to][e.rev].cap += pushed;             // increase reverse residual
35                     return pushed;
36                 }
37             }
38         }
39         return 0; // no augmenting path from this vertex
40     }
41 
42     long long max_flow(int s, int t) {
43         long long flow = 0;
44         while (true) {
45             vector<int> vis(n, 0);            // must reset each augmentation
46             long long pushed = dfs(s, t, LLONG_MAX, vis);
47             if (pushed == 0) break;           // no more augmenting paths
48             flow += pushed;
49         }
50         return flow;
51     }
52 };
53 
54 int main() {
55     ios::sync_with_stdio(false);
56     cin.tie(nullptr);
57 
58     int n, m; // number of vertices and edges
59     if (!(cin >> n >> m)) return 0;
60     MaxFlowDFS mf(n);
61     for (int i = 0; i < m; ++i) {
62         int u, v; long long c;
63         cin >> u >> v >> c; // assume 0-based vertices
64         mf.add_edge(u, v, c);
65     }
66     int s, t; cin >> s >> t;
67     cout << mf.max_flow(s, t) << "\n";
68     return 0;
69 }
70

This program implements the classic Ford–Fulkerson method using recursive DFS to find augmenting paths. The residual graph stores both forward and reverse edges. Each DFS call attempts to push as much flow as possible to the sink, bounded by encountered residual capacities; when it reaches the sink, we propagate the bottleneck upward and update residual capacities along the path. We repeat until DFS can no longer reach t from s. This is simple and often fast on small instances with small integer capacities.

Time: O(E · F) for integer capacities (E = number of edges, F = max flow value).Space: O(V + E) to store the residual graph.

Edmonds–Karp (BFS-based Ford–Fulkerson)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge {
5     int to;
6     long long cap;
7     int rev;
8 };
9 
10 struct EdmondsKarp {
11     int n;
12     vector<vector<Edge>> g;
13 
14     EdmondsKarp(int n): n(n), g(n) {}
15 
16     void add_edge(int u, int v, long long c) {
17         Edge a{v, c, (int)g[v].size()};
18         Edge b{u, 0, (int)g[u].size()};
19         g[u].push_back(a);
20         g[v].push_back(b);
21     }
22 
23     long long bfs(int s, int t, vector<int>& pv, vector<int>& pe) {
24         fill(pv.begin(), pv.end(), -1);
25         fill(pe.begin(), pe.end(), -1);
26         queue<int> q;
27         q.push(s);
28         pv[s] = s; // mark source as visited with itself as parent
29         while (!q.empty()) {
30             int v = q.front(); q.pop();
31             if (v == t) break;
32             for (int i = 0; i < (int)g[v].size(); ++i) {
33                 const Edge &e = g[v][i];
34                 if (pv[e.to] == -1 && e.cap > 0) {
35                     pv[e.to] = v;  // parent vertex
36                     pe[e.to] = i;  // index of edge used from parent to this node
37                     q.push(e.to);
38                 }
39             }
40         }
41         if (pv[t] == -1) return 0; // no path
42         long long add = LLONG_MAX;
43         // find bottleneck by walking back from t
44         for (int v = t; v != s; v = pv[v]) {
45             int u = pv[v];
46             int ei = pe[v];
47             add = min(add, g[u][ei].cap);
48         }
49         // apply augmentation
50         for (int v = t; v != s; v = pv[v]) {
51             int u = pv[v];
52             int ei = pe[v];
53             int ri = g[u][ei].rev;
54             g[u][ei].cap -= add;
55             g[v][ri].cap += add;
56         }
57         return add;
58     }
59 
60     long long max_flow(int s, int t) {
61         vector<int> pv(n), pe(n);
62         long long flow = 0;
63         while (true) {
64             long long pushed = bfs(s, t, pv, pe);
65             if (pushed == 0) break;
66             flow += pushed;
67         }
68         return flow;
69     }
70 };
71 
72 int main() {
73     ios::sync_with_stdio(false);
74     cin.tie(nullptr);
75 
76     int n, m; if (!(cin >> n >> m)) return 0;
77     EdmondsKarp ek(n);
78     for (int i = 0; i < m; ++i) {
79         int u, v; long long c; cin >> u >> v >> c; // 0-based
80         ek.add_edge(u, v, c);
81     }
82     int s, t; cin >> s >> t;
83     cout << ek.max_flow(s, t) << "\n";
84     return 0;
85 }
86

This is the BFS variant (Edmonds–Karp). BFS finds the shortest augmenting path in terms of edges, ensuring a polynomial number of augmentations. The parent arrays (pv, pe) record how we reached each node; reconstructing from t to s yields the bottleneck, then we update forward and reverse residual capacities along the path.

Time: O(V · E^2).Space: O(V + E).

Capacity Scaling Ford–Fulkerson (BFS restricted by threshold)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge {
5     int to;
6     long long cap;
7     int rev;
8 };
9 
10 struct ScalingMaxFlow {
11     int n;
12     vector<vector<Edge>> g;
13     long long U = 0; // track maximum capacity added
14 
15     ScalingMaxFlow(int n): n(n), g(n) {}
16 
17     void add_edge(int u, int v, long long c) {
18         Edge a{v, c, (int)g[v].size()};
19         Edge b{u, 0, (int)g[u].size()};
20         g[u].push_back(a);
21         g[v].push_back(b);
22         U = max(U, c);
23     }
24 
25     // BFS that only follows edges with residual >= delta
26     long long bfs_with_threshold(int s, int t, long long delta, vector<int>& pv, vector<int>& pe) {
27         fill(pv.begin(), pv.end(), -1);
28         fill(pe.begin(), pe.end(), -1);
29         queue<int> q; q.push(s); pv[s] = s;
30         while (!q.empty()) {
31             int v = q.front(); q.pop();
32             if (v == t) break;
33             for (int i = 0; i < (int)g[v].size(); ++i) {
34                 const Edge &e = g[v][i];
35                 if (pv[e.to] == -1 && e.cap >= delta) {
36                     pv[e.to] = v; pe[e.to] = i; q.push(e.to);
37                 }
38             }
39         }
40         if (pv[t] == -1) return 0;
41         long long add = LLONG_MAX;
42         for (int v = t; v != s; v = pv[v]) {
43             int u = pv[v]; int ei = pe[v];
44             add = min(add, g[u][ei].cap);
45         }
46         for (int v = t; v != s; v = pv[v]) {
47             int u = pv[v]; int ei = pe[v]; int ri = g[u][ei].rev;
48             g[u][ei].cap -= add;
49             g[v][ri].cap += add;
50         }
51         return add;
52     }
53 
54     long long max_flow(int s, int t) {
55         long long flow = 0;
56         if (U == 0) return 0;
57         long long delta = 1;
58         while (delta <= U) delta <<= 1; // delta = 2^k > U
59         delta >>= 1; // largest power of two <= U
60         vector<int> pv(n), pe(n);
61         while (delta > 0) {
62             while (true) {
63                 long long pushed = bfs_with_threshold(s, t, delta, pv, pe);
64                 if (pushed == 0) break;
65                 flow += pushed;
66             }
67             delta >>= 1; // decrease threshold
68         }
69         return flow;
70     }
71 };
72 
73 int main() {
74     ios::sync_with_stdio(false);
75     cin.tie(nullptr);
76 
77     int n, m; if (!(cin >> n >> m)) return 0;
78     ScalingMaxFlow mf(n);
79     for (int i = 0; i < m; ++i) {
80         int u, v; long long c; cin >> u >> v >> c; // 0-based
81         mf.add_edge(u, v, c);
82     }
83     int s, t; cin >> s >> t;
84     cout << mf.max_flow(s, t) << "\n";
85     return 0;
86 }
87

Capacity scaling prefers augmenting along large-capacity edges first by enforcing a threshold Δ that halves each phase. BFS is restricted to edges with residual capacity at least Δ, which reduces the number of small, unproductive pushes when capacities vary widely. The resulting algorithm keeps the same residual-graph structure and correctness guarantees while often improving runtime in practice.

Time: O(E^2 log U), where U is the maximum edge capacity.Space: O(V + E).

Max Flow with Min-Cut Extraction (report partition and cut edges)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Edge {
5     int to;
6     long long cap;
7     int rev;
8 };
9 
10 struct EdmondsKarpWithCut {
11     int n;
12     vector<vector<Edge>> g;
13     vector<tuple<int,int,long long>> original; // (u,v,c) for reporting min cut
14 
15     EdmondsKarpWithCut(int n): n(n), g(n) {}
16 
17     void add_edge(int u, int v, long long c) {
18         Edge a{v, c, (int)g[v].size()};
19         Edge b{u, 0, (int)g[u].size()};
20         g[u].push_back(a);
21         g[v].push_back(b);
22         original.emplace_back(u, v, c);
23     }
24 
25     long long bfs(int s, int t, vector<int>& pv, vector<int>& pe) {
26         fill(pv.begin(), pv.end(), -1);
27         fill(pe.begin(), pe.end(), -1);
28         queue<int> q; q.push(s); pv[s] = s;
29         while (!q.empty()) {
30             int v = q.front(); q.pop();
31             if (v == t) break;
32             for (int i = 0; i < (int)g[v].size(); ++i) {
33                 const Edge &e = g[v][i];
34                 if (pv[e.to] == -1 && e.cap > 0) {
35                     pv[e.to] = v; pe[e.to] = i; q.push(e.to);
36                 }
37             }
38         }
39         if (pv[t] == -1) return 0;
40         long long add = LLONG_MAX;
41         for (int v = t; v != s; v = pv[v]) {
42             int u = pv[v]; int ei = pe[v];
43             add = min(add, g[u][ei].cap);
44         }
45         for (int v = t; v != s; v = pv[v]) {
46             int u = pv[v]; int ei = pe[v]; int ri = g[u][ei].rev;
47             g[u][ei].cap -= add;
48             g[v][ri].cap += add;
49         }
50         return add;
51     }
52 
53     long long max_flow(int s, int t) {
54         vector<int> pv(n), pe(n);
55         long long flow = 0;
56         while (true) {
57             long long pushed = bfs(s, t, pv, pe);
58             if (pushed == 0) break;
59             flow += pushed;
60         }
61         return flow;
62     }
63 
64     vector<int> min_cut_reachable(int s) {
65         // BFS on residual graph to find vertices reachable from s
66         vector<int> vis(n, 0); queue<int> q; q.push(s); vis[s] = 1;
67         while (!q.empty()) {
68             int v = q.front(); q.pop();
69             for (auto &e : g[v]) {
70                 if (!vis[e.to] && e.cap > 0) {
71                     vis[e.to] = 1; q.push(e.to);
72                 }
73             }
74         }
75         return vis; // vis[v]=1 means v in S; otherwise in T
76     }
77 };
78 
79 int main() {
80     ios::sync_with_stdio(false);
81     cin.tie(nullptr);
82 
83     int n, m; if (!(cin >> n >> m)) return 0;
84     EdmondsKarpWithCut solver(n);
85     for (int i = 0; i < m; ++i) {
86         int u, v; long long c; cin >> u >> v >> c; // 0-based
87         solver.add_edge(u, v, c);
88     }
89     int s, t; cin >> s >> t;
90     long long maxflow = solver.max_flow(s, t);
91     vector<int> reach = solver.min_cut_reachable(s);
92 
93     // Report min cut partition and crossing edges (u in S, v in T)
94     long long cutCap = 0;
95     vector<pair<int,int>> cutEdges;
96     for (auto [u, v, c] : solver.original) {
97         if (reach[u] && !reach[v] && c > 0) {
98             cutCap += c;
99             cutEdges.emplace_back(u, v);
100         }
101     }
102 
103     cout << "max_flow " << maxflow << "\n";
104     cout << "min_cut_capacity " << cutCap << "\n";
105     cout << "S: ";
106     for (int i = 0; i < n; ++i) if (reach[i]) cout << i << ' ';
107     cout << "\nT: ";
108     for (int i = 0; i < n; ++i) if (!reach[i]) cout << i << ' ';
109     cout << "\ncut_edges_count " << cutEdges.size() << "\n";
110     for (auto [u, v] : cutEdges) cout << u << ' ' << v << "\n";
111     return 0;
112 }
113

We compute max flow with Edmonds–Karp, then run a BFS on the residual graph to find the set S of vertices reachable from s. By the Max-Flow Min-Cut Theorem, the edges from S to its complement T (in the original graph) that cross the partition and have positive original capacity form a minimum s–t cut, and their total capacity equals the max flow. The program prints the max flow, the min-cut capacity, the partition, and the list of cut edges.

Time: Max flow: O(V · E^2); min-cut extraction: O(V + E).Space: O(V + E).

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Edge {
5	int to; // destination vertex
6	long long cap; // residual capacity on this edge
7	int rev; // index of the reverse edge in g[to]
8	};
9
10	struct MaxFlowDFS {
11	int n;
12	vector<vector<Edge>> g; // residual graph
13
14	MaxFlowDFS(int n): n(n), g(n) {}
15
16	void add_edge(int u, int v, long long c) {
17	// forward edge u->v with capacity c
18	Edge a{v, c, (int)g[v].size()};
19	// reverse edge v->u with initial 0 capacity
20	Edge b{u, 0, (int)g[u].size()};
21	g[u].push_back(a);
22	g[v].push_back(b);
23	}
24
25	long long dfs(int v, int t, long long f, vector<int>& vis) {
26	if (v == t) return f; // reached sink, can push f
27	vis[v] = 1;
28	for (auto &e : g[v]) {
29	if (!vis[e.to] && e.cap > 0) {
30	long long pushed = dfs(e.to, t, min(f, e.cap), vis);
31	if (pushed > 0) {
32	// use residual capacities to update
33	e.cap -= pushed; // reduce forward residual
34	g[e.to][e.rev].cap += pushed; // increase reverse residual
35	return pushed;
36	}
37	}
38	}
39	return 0; // no augmenting path from this vertex
40	}
41
42	long long max_flow(int s, int t) {
43	long long flow = 0;
44	while (true) {
45	vector<int> vis(n, 0); // must reset each augmentation
46	long long pushed = dfs(s, t, LLONG_MAX, vis);
47	if (pushed == 0) break; // no more augmenting paths
48	flow += pushed;
49	}
50	return flow;
51	}
52	};
53
54	int main() {
55	ios::sync_with_stdio(false);
56	cin.tie(nullptr);
57
58	int n, m; // number of vertices and edges
59	if (!(cin >> n >> m)) return 0;
60	MaxFlowDFS mf(n);
61	for (int i = 0; i < m; ++i) {
62	int u, v; long long c;
63	cin >> u >> v >> c; // assume 0-based vertices
64	mf.add_edge(u, v, c);
65	}
66	int s, t; cin >> s >> t;
67	cout << mf.max_flow(s, t) << "\n";
68	return 0;
69	}
70