⚙️AlgorithmIntermediate

Maximum Flow - Dinic's Algorithm

Key Points

•
Dinic's algorithm computes maximum flow by repeatedly building a level graph with BFS and sending a blocking flow using DFS.
•
Each phase increases the shortest path distance from source to sink, guaranteeing progress until the sink becomes unreachable.
•
The general worst-case time complexity is O( $V^{2}$ E), but it is much faster on many real inputs.
•
For bipartite matching (unit capacities), Dinic runs in O(E $V$ ) and is highly competitive.
•
On general unit-capacity networks, Dinic runs in O(E $V^{2/3}$ ), which is significantly better than the general bound.
•
The current-arc optimization ensures each edge is scanned only a constant number of times per phase, making blocking-flow computation efficient.
•
Residual edges with reverse capacities are crucial for flow cancellation and augmenting along alternative routes.
•
After max flow, the reachable set in the residual graph from the source identifies a minimum s–t cut by the Max-Flow Min-Cut Theorem.

Prerequisites

→Graphs and adjacency lists — You need to represent directed graphs efficiently and traverse them.
→BFS and DFS — Dinic uses BFS to build levels and DFS to send blocking flow.
→Big-O analysis — Understanding O(V^2 E), O(E \sqrt{V}), and why per-phase work is linear in E is crucial.
→Residual networks and augmenting paths — Dinic relies on residual capacities and reverse edges to adjust previous flow decisions.
→Bipartite graphs and matchings — A key application of Dinic is maximum bipartite matching with unit capacities.

Detailed Explanation

Tap terms for definitions

01Overview

Maximum flow asks: given a directed network with capacities on edges, how much "stuff" can we push from a source to a sink without violating any capacity? Dinic's algorithm is a practical and powerful solution. It improves over simpler augmenting-path methods by batching many augmentations in one go. The core idea is to build a level graph using BFS that keeps only edges that go from a level to the next level (shortest-path layers). Then, within this level graph, the algorithm finds a blocking flow: a set of augmentations such that every s–t path in the level graph has at least one saturated edge, preventing further progress at the same distance. This blocking flow is computed efficiently with DFS guided by a current-arc pointer so that each edge is considered only a few times per phase. After pushing a blocking flow, the level graph is rebuilt; each time, the shortest distance from source to sink strictly increases, leading to eventual termination when the sink becomes unreachable. While the theoretical worst-case time is O(V^2 E), Dinic is often much faster in practice and has excellent guarantees for special cases like bipartite matching and unit-capacity networks.

02Intuition & Analogies

Imagine a city trying to evacuate people from a source area (s) to a safe zone (t) using one-way roads with capacity limits. You first plan the shortest number of intersections to reach safety using only roads in the proper direction—this is your quick evacuation blueprint (the level graph). Then you send as many buses as possible along these shortest-layered routes. Quickly, some roads become jammed (saturated). Once every shortest route has at least one jammed road, you can’t send more along those distances—this is the blocking flow. Next, you update your blueprint: because some roads are full, the shortest number of steps to reach safety might increase. You repeat: rebuild the shortest-route map and again flood as many buses as possible through it. Eventually, the safe zone becomes unreachable on any path that respects capacity; that means you’ve evacuated the maximum number of people given the road limits. The reverse roads in the residual network are like sent-back buses: if you realize a previous routing decision was suboptimal, you can take a reverse edge (cancel part of a prior assignment) and reroute flow elsewhere. The current-arc trick is like remembering the last road you tried from an intersection so you don’t waste time retrying already-full streets. This disciplined exploration lets Dinic find big batches of flow in each round and is why it’s both elegant and fast in contest settings.

03Formal Definition

Let G = (V, E) be a directed graph with capacity function c: E

\to

R_{\geq 0}

, source s

\in

V and sink t

\in

V. A flow is a function f: E

\to

R_{\geq 0}

that satisfies: (1) Capacity constraints: 0

\leq

f(e)

\leq

c(e) for all e

\in

E; (2) Flow conservation: for all v

\in

∖

\{s,t\},

\sum_{u : (u, v) \in E}

f(u,v) =

\sum_{w : (v, w) \in E}

f(v,w). The value of a flow is

∣ f ∣

\sum_{w : (s, w) \in E}

f(s,w). The residual capacity of edge (u,v) with respect to f is

r_{f}

(u,v) = c(u,v) - f(u,v); if f(u,v) > 0, a reverse residual edge (v,u) with capacity f(u,v) is available. Dinic’s algorithm proceeds in phases. In each phase, it builds the level graph L by BFS from s on the residual network, keeping only edges (u,v) with

r_{f}

(u,v) > 0 and

level

(v) =

level

(u) + 1. Then it finds a blocking flow g in L: a feasible flow in L such that every s–t path in L contains at least one saturated edge in g. The algorithm augments f by g, updates the residual network, and repeats until t is unreachable from s in the residual graph. The final flow is maximum, and by the Max-Flow Min-Cut Theorem its value equals the capacity of a minimum s–t cut.

04When to Use

Use Dinic’s algorithm when you need exact maximum flow with strong practical performance and relatively simple implementation. It shines in competitive programming for: (1) Bipartite matching and assignment with unit capacities where it achieves O(E \sqrt{V}) and is straightforward to code; (2) Problems requiring repeated shortest-layered augmentation, such as computing disjoint paths or scheduling with precedence constraints mapped to flow; (3) Medium-to-large sparse graphs where E is up to roughly 2e5–1e6 and capacities fit in 64-bit integers; (4) Extracting minimum cuts after computing max flow for partitioning tasks; (5) Multi-source or multi-sink problems that can be reduced by adding a super-source/sink. Prefer Dinic over Edmonds–Karp when you find Edmonds–Karp too slow (O(VE^2)), and prefer Dinic over Push–Relabel if you need simpler code, predictable layering behavior, or the special-case guarantees for unit-capacity networks and bipartite graphs. For extremely dense graphs or when you need the fastest asymptotics on arbitrary capacities, the highest-label push–relabel with heuristics might be faster, but Dinic is usually competitive and easier to debug.

⚠️Common Mistakes

• Forgetting reverse edges or giving them the wrong initial capacity (should start at 0) breaks the residual graph and prevents correct cancellation of flow. • Not resetting the level array and current-arc pointers between phases causes incorrect traversal and missed augmentations. • Using 32-bit int for capacities can overflow; prefer 64-bit (long long) when sums of flows may exceed 2e9. • Treating undirected edges as a single edge instead of two oppositely directed edges with the given capacity can double-count or miss capacity. • Writing DFS that ignores the level condition (only go from level u to level v = level u + 1) turns Dinic into an incorrect algorithm. • Not checking for zero return from DFS and still advancing the current pointer can lead to infinite loops or TLE; always move current-arc when an edge is fully explored or saturated. • Recursion depth can be large on deep graphs; either increase stack limits or implement iterative DFS if needed. • In bipartite matching extraction, forgetting that only original left-to-right edges with residual capacity 0 are matched leads to wrong pairs. • Building the level graph with BFS but allowing edges with zero residual capacity wastes time; ensure r_f(u,v) > 0. • Assuming the general O(V^2 E) bound will always be observed in practice; in contests, inputs are often favorable, but still code with linear-time-per-phase optimizations.

Key Formulas

Capacity constraints

\forall (u, v) \in E : 0 \leq f_{uv} \leq c_{uv}

Explanation: Flow on any edge cannot exceed its capacity and cannot be negative. This bounds the feasible region for the flow.

Flow conservation

\forall v \in V ∖ {s, t} : u : (u, v) \in E \sum f_{uv} = w : (v, w) \in E \sum f_{v w}

Explanation: Except at the source and sink, the total incoming flow equals the total outgoing flow. This enforces that intermediate nodes neither create nor destroy flow.

Value of a flow

∣ f ∣ = w : (s, w) \in E \sum f_{s w} = u : (u, t) \in E \sum f_{u t}

Explanation: The flow value equals net outflow from the source and also net inflow to the sink. Both are equal for any feasible flow.

Residual capacity

r_{f} (u, v) = c_{uv} - f_{uv}

Explanation: The residual capacity indicates how much more flow can be pushed forward on (u,v). Reverse residual capacity $r_{f}$ (v,u) equals the current flow $f_{uv}$ .

Cut capacity

c (S, T) = u \in S, v \in T \sum c_{uv}

Explanation: The capacity of a cut (S,T) is the sum of capacities of all edges going from S to T. It upper-bounds any s–t flow value.

Max-Flow Min-Cut Theorem

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

Explanation: The maximum value of a feasible flow equals the minimum capacity among all s–t cuts. Dinic’s algorithm implicitly certifies this by producing a cut when the sink becomes unreachable.

Dinic general bound

T (n) = O (V^{2} E)

Explanation: In the worst case on arbitrary capacities, Dinic requires O( $V^{2}$ ) phases and each phase takes O(E) time. Hence the overall time is O( $V^{2}$ E).

Bipartite matching bound

T (n) = O (E V)

Explanation: On bipartite graphs with unit capacities, the number of phases is O( $V$ ) and each phase is O(E), yielding O(E $\sqrt$ {V)).

Unit-capacity bound

T (n) = O (E V^{2/3})

Explanation: For general unit-capacity networks, fewer phases are needed—O( $V^{2/3}$ ). With O(E) time per phase, total time is O(E $V^{2/3}$ ).

Complexity Analysis

Dinic’s algorithm proceeds in phases. Each phase builds a level graph by BFS in O(E) time (assuming adjacency lists). Then it computes a blocking flow restricted to this acyclic, layered graph. With the current-arc optimization, the total work of all DFS calls in a single phase is O(E): each directed edge is considered a constant number of times before it becomes either saturated or proven useless for this phase. Hence, one phase costs O(E) time and O(V) additional memory for levels and current-arc pointers; the residual graph shares space with the edge list, which is O(E). The total number of phases depends on graph structure and capacities. In the general case with arbitrary capacities, the sink’s level can increase only O(V) times, but a delicate worst-case construction forces O(

V^{2}

) phases, giving O(

V^{2}

E) time overall. In practice this extreme behavior is rare. For special cases, the number of phases is much smaller: on bipartite graphs with unit capacities (e.g., maximum matching), Dinic runs in O(E

V

). On general unit-capacity networks (not necessarily bipartite), the bound improves to O(E

V^{2/3}

). Space complexity is O(V + E): we store for each edge its head, residual capacity, and an index to the paired reverse edge; plus arrays of size O(V) for levels, iterators, and the BFS queue. If you augment the implementation to also store original capacities for min-cut extraction or to reconstruct solutions (e.g., matchings), space remains linear in E. The recursion depth of DFS is at most O(V), so iterative variants or increased stack size may be needed for very deep graphs.

Code Examples

Dinic's Algorithm (Generic, 64-bit capacities) with Min-Cut Extraction

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Dinic {
5     struct Edge {
6         int to;            // destination vertex
7         long long cap;     // residual capacity on this edge
8         int rev;           // index of the reverse edge in adj[to]
9     };
10 
11     int N;                       // number of vertices
12     int s, t;                    // source and sink
13     vector<vector<Edge>> adj;    // adjacency list of residual graph
14     vector<int> level;           // BFS levels
15     vector<int> cur;             // current-arc pointer for DFS
16 
17     Dinic(int n): N(n), s(0), t(n-1), adj(n), level(n), cur(n) {}
18 
19     void set_source_sink(int S, int T) { s = S; t = T; }
20 
21     // Add a directed edge u->v with capacity cap
22     void add_edge(int u, int v, long long cap) {
23         Edge a{v, cap, (int)adj[v].size()};
24         Edge b{u, 0LL,   (int)adj[u].size()}; // reverse edge with 0 initial cap
25         adj[u].push_back(a);
26         adj[v].push_back(b);
27     }
28 
29     // BFS builds level graph; returns true if t is reachable
30     bool bfs() {
31         fill(level.begin(), level.end(), -1);
32         queue<int> q;
33         level[s] = 0;
34         q.push(s);
35         while (!q.empty()) {
36             int u = q.front(); q.pop();
37             for (const auto &e : adj[u]) {
38                 if (e.cap > 0 && level[e.to] == -1) {
39                     level[e.to] = level[u] + 1;
40                     q.push(e.to);
41                 }
42             }
43         }
44         return level[t] != -1;
45     }
46 
47     // DFS sends flow on level graph, limited by 'f'
48     long long dfs(int u, long long f) {
49         if (u == t || f == 0) return f;
50         for (int &i = cur[u]; i < (int)adj[u].size(); ++i) { // current-arc optimization
51             Edge &e = adj[u][i];
52             if (e.cap > 0 && level[e.to] == level[u] + 1) {
53                 long long pushed = dfs(e.to, min(f, e.cap));
54                 if (pushed > 0) {
55                     e.cap -= pushed;                       // reduce residual on forward edge
56                     adj[e.to][e.rev].cap += pushed;        // increase residual on reverse edge
57                     return pushed;
58                 }
59             }
60         }
61         return 0LL; // no more augmenting from u in current level graph
62     }
63 
64     long long max_flow() {
65         long long flow = 0;
66         while (bfs()) {                // build new level graph
67             fill(cur.begin(), cur.end(), 0);
68             while (true) {             // send blocking flow
69                 long long pushed = dfs(s, LLONG_MAX);
70                 if (pushed == 0) break;
71                 flow += pushed;
72             }
73         }
74         return flow;
75     }
76 
77     // After max_flow, compute the min-cut: nodes reachable from s in residual graph
78     vector<int> min_cut_side_S() {
79         vector<int> vis(N, 0);
80         queue<int> q;
81         q.push(s); vis[s] = 1;
82         while (!q.empty()) {
83             int u = q.front(); q.pop();
84             for (auto &e : adj[u]) {
85                 if (e.cap > 0 && !vis[e.to]) {
86                     vis[e.to] = 1;
87                     q.push(e.to);
88                 }
89             }
90         }
91         return vis; // vis[v]=1 if v in S-side; else T-side
92     }
93 };
94 
95 int main() {
96     ios::sync_with_stdio(false);
97     cin.tie(nullptr);
98 
99     // Example: small graph
100     // 0(s) -> 1 (10), 0 -> 2 (5), 1 -> 2 (15), 1 -> 3 (10), 2 -> 4 (10), 3 -> 4 (10), 4(t)=5? We'll use 5 nodes with t=4.
101     int n = 5;
102     int s = 0, t = 4;
103     Dinic D(n);
104     D.set_source_sink(s, t);
105 
106     D.add_edge(0, 1, 10);
107     D.add_edge(0, 2, 5);
108     D.add_edge(1, 2, 15);
109     D.add_edge(1, 3, 10);
110     D.add_edge(2, 4, 10);
111     D.add_edge(3, 4, 10);
112 
113     long long ans = D.max_flow();
114     cout << "Max flow = " << ans << "\n";
115 
116     auto S = D.min_cut_side_S();
117     cout << "Min-cut edges (S->T):\n";
118     for (int u = 0; u < n; ++u) if (S[u]) {
119         for (auto &e : D.adj[u]) {
120             // If e is a forward residual edge now (cap may be < original), we can't easily know original capacity without storing it.
121             // For demonstration, print edges that cross from S to non-S and currently have zero residual cap on forward edge (likely saturated in min-cut).
122             if (!S[e.to]) {
123                 cout << u << " -> " << e.to << " (residual cap now = " << e.cap << ")\n";
124             }
125         }
126     }
127     return 0;
128 }
129

This is a standard Dinic implementation. BFS builds the level graph; DFS with a current-arc pointer pushes flow along level-respecting paths to build a blocking flow. We loop phases until the sink becomes unreachable. After computing max flow, a BFS on edges with positive residual capacity finds the S-side of a minimum cut by reachability from s.

Time: O(V^2 E) in general; O(E \sqrt{V}) on bipartite/unit-matching; O(E V^{2/3}) on general unit-capacity networksSpace: O(V + E)

Maximum Bipartite Matching using Dinic (unit capacities)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Dinic {
5     struct Edge { int to; int rev; int cap; };
6     int N, s, t; 
7     vector<vector<Edge>> g; 
8     vector<int> level, cur;
9     Dinic(int n): N(n), s(0), t(n-1), g(n), level(n), cur(n) {}
10     void set_source_sink(int S, int T) { s=S; t=T; }
11     void add_edge(int u, int v, int cap) {
12         Edge a{v, (int)g[v].size(), cap};
13         Edge b{u, (int)g[u].size(), 0};
14         g[u].push_back(a); g[v].push_back(b);
15     }
16     bool bfs(){ fill(level.begin(), level.end(), -1); queue<int>q; level[s]=0; q.push(s);
17         while(!q.empty()){ int u=q.front(); q.pop();
18             for(auto &e:g[u]) if(e.cap>0 && level[e.to]==-1){ level[e.to]=level[u]+1; q.push(e.to);} }
19         return level[t]!=-1; }
20     int dfs(int u, int f){ if(u==t||!f) return f; for(int &i=cur[u]; i<(int)g[u].size(); ++i){ auto &e=g[u][i];
21             if(e.cap>0 && level[e.to]==level[u]+1){ int pushed=dfs(e.to, min(f, e.cap)); if(pushed){ e.cap-=pushed; g[e.to][e.rev].cap+=pushed; return pushed; } } }
22         return 0; }
23     int max_flow(){ int flow=0; while(bfs()){ fill(cur.begin(), cur.end(), 0); while(int pushed=dfs(s, INT_MAX)) flow+=pushed; } return flow; }
24 };
25 
26 int main(){
27     ios::sync_with_stdio(false); cin.tie(nullptr);
28     // Left part L size = 3, Right part R size = 3. Nodes: 0=source, 1..3=L, 4..6=R, 7=sink
29     int L=3, R=3; int S=0, T=L+R+1; int N=T+1;
30     Dinic D(N); D.set_source_sink(S, T);
31 
32     // Connect source to left with cap 1; right to sink with cap 1
33     for(int i=1;i<=L;i++) D.add_edge(S, i, 1);
34     for(int j=1;j<=R;j++) D.add_edge(L+j, T, 1);
35 
36     // Add edges L->R (unit capacity): pairs (1,1), (1,2), (2,2), (3,2), (3,3)
37     D.add_edge(1, L+1, 1);
38     D.add_edge(1, L+2, 1);
39     D.add_edge(2, L+2, 1);
40     D.add_edge(3, L+2, 1);
41     D.add_edge(3, L+3, 1);
42 
43     int matching = D.max_flow();
44     cout << "Maximum matching size = " << matching << "\n";
45 
46     // Recover matched pairs: original L->R edges with residual cap 0 are matched
47     for(int u=1; u<=L; ++u){
48         for(auto &e : D.g[u]){
49             if(e.to>=1+L && e.to<=L+R){ // L->R edge
50                 int v=e.to - L;         // right index
51                 if(e.cap==0){           // saturated => matched
52                     cout << "L" << u << " - R" << v << "\n";
53                 }
54             }
55         }
56     }
57     return 0;
58 }
59

We build a standard flow network for bipartite matching: source connects to all left nodes, left-to-right edges have capacity 1, and right nodes connect to sink with capacity 1. Dinic finds the maximum matching. We then reconstruct matched pairs by checking which original L→R edges were saturated.

Time: O(E \sqrt{V})Space: O(V + E)

Multiple Sources and Sinks via Super-Source/Super-Sink (Dinic)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Dinic {
5     struct Edge{ int to, rev; long long cap; };
6     int N, s, t; vector<vector<Edge>> g; vector<int> level, cur;
7     Dinic(int n): N(n), s(0), t(n-1), g(n), level(n), cur(n) {}
8     void set_source_sink(int S, int T){ s=S; t=T; }
9     void add_edge(int u,int v,long long c){ Edge a{v,(int)g[v].size(),c}; Edge b{u,(int)g[u].size(),0}; g[u].push_back(a); g[v].push_back(b);}    
10     bool bfs(){ fill(level.begin(), level.end(), -1); queue<int>q; level[s]=0; q.push(s);
11         while(!q.empty()){ int u=q.front(); q.pop(); for(auto &e:g[u]) if(e.cap>0 && level[e.to]==-1){ level[e.to]=level[u]+1; q.push(e.to);} } return level[t]!=-1; }
12     long long dfs(int u,long long f){ if(u==t||!f) return f; for(int &i=cur[u]; i<(int)g[u].size(); ++i){ auto &e=g[u][i]; if(e.cap>0 && level[e.to]==level[u]+1){ long long p=dfs(e.to, min(f, e.cap)); if(p){ e.cap-=p; g[e.to][e.rev].cap+=p; return p; } } } return 0; }
13     long long max_flow(){ long long F=0; while(bfs()){ fill(cur.begin(), cur.end(), 0); while(long long p=dfs(s, LLONG_MAX)) F+=p; } return F; }
14 };
15 
16 int main(){
17     ios::sync_with_stdio(false); cin.tie(nullptr);
18 
19     // Suppose original graph has nodes 0..5; sources = {0,1}, sinks = {4,5}
20     // We'll create super-source S=6, super-sink T=7
21     int origN=6; int S=origN, T=origN+1; int N=origN+2;
22     Dinic D(N); D.set_source_sink(S, T);
23 
24     auto add_undir = [&](int u,int v,long long c){ // example: undirected capacity modeled as two directed edges
25         D.add_edge(u, v, c);
26         D.add_edge(v, u, c);
27     };
28 
29     // Example internal edges
30     add_undir(0,2,5);
31     add_undir(1,2,3);
32     D.add_edge(2,3,4);
33     D.add_edge(3,4,3);
34     D.add_edge(2,5,2);
35 
36     // Connect super-source to real sources with INF caps
37     const long long INF = (long long)4e18;
38     D.add_edge(S, 0, INF);
39     D.add_edge(S, 1, INF);
40 
41     // Connect real sinks to super-sink
42     D.add_edge(4, T, INF);
43     D.add_edge(5, T, INF);
44 
45     cout << "Max multi-source/multi-sink flow = " << D.max_flow() << "\n";
46     return 0;
47 }
48

Many problems have multiple sources and sinks. We reduce them to a single max-flow instance by adding a super-source connected to all real sources and a super-sink connected to all real sinks with sufficiently large capacities. The rest of the network is unchanged, and Dinic runs as usual.

Time: Same as standard Dinic on the expanded graph: O(V'^2 E') in generalSpace: O(V' + E') where V' and E' are after adding super nodes and edges

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Dinic {
5	struct Edge {
6	int to; // destination vertex
7	long long cap; // residual capacity on this edge
8	int rev; // index of the reverse edge in adj[to]
9	};
10
11	int N; // number of vertices
12	int s, t; // source and sink
13	vector<vector<Edge>> adj; // adjacency list of residual graph
14	vector<int> level; // BFS levels
15	vector<int> cur; // current-arc pointer for DFS
16
17	Dinic(int n): N(n), s(0), t(n-1), adj(n), level(n), cur(n) {}
18
19	void set_source_sink(int S, int T) { s = S; t = T; }
20
21	// Add a directed edge u->v with capacity cap
22	void add_edge(int u, int v, long long cap) {
23	Edge a{v, cap, (int)adj[v].size()};
24	Edge b{u, 0LL, (int)adj[u].size()}; // reverse edge with 0 initial cap
25	adj[u].push_back(a);
26	adj[v].push_back(b);
27	}
28
29	// BFS builds level graph; returns true if t is reachable
30	bool bfs() {
31	fill(level.begin(), level.end(), -1);
32	queue<int> q;
33	level[s] = 0;
34	q.push(s);
35	while (!q.empty()) {
36	int u = q.front(); q.pop();
37	for (const auto &e : adj[u]) {
38	if (e.cap > 0 && level[e.to] == -1) {
39	level[e.to] = level[u] + 1;
40	q.push(e.to);
41	}
42	}
43	}
44	return level[t] != -1;
45	}
46
47	// DFS sends flow on level graph, limited by 'f'
48	long long dfs(int u, long long f) {
49	if (u == t \|\| f == 0) return f;
50	for (int &i = cur[u]; i < (int)adj[u].size(); ++i) { // current-arc optimization
51	Edge &e = adj[u][i];
52	if (e.cap > 0 && level[e.to] == level[u] + 1) {
53	long long pushed = dfs(e.to, min(f, e.cap));
54	if (pushed > 0) {
55	e.cap -= pushed; // reduce residual on forward edge
56	adj[e.to][e.rev].cap += pushed; // increase residual on reverse edge
57	return pushed;
58	}
59	}
60	}
61	return 0LL; // no more augmenting from u in current level graph
62	}
63
64	long long max_flow() {
65	long long flow = 0;
66	while (bfs()) { // build new level graph
67	fill(cur.begin(), cur.end(), 0);
68	while (true) { // send blocking flow
69	long long pushed = dfs(s, LLONG_MAX);
70	if (pushed == 0) break;
71	flow += pushed;
72	}
73	}
74	return flow;
75	}
76
77	// After max_flow, compute the min-cut: nodes reachable from s in residual graph
78	vector<int> min_cut_side_S() {
79	vector<int> vis(N, 0);
80	queue<int> q;
81	q.push(s); vis[s] = 1;
82	while (!q.empty()) {
83	int u = q.front(); q.pop();
84	for (auto &e : adj[u]) {
85	if (e.cap > 0 && !vis[e.to]) {
86	vis[e.to] = 1;
87	q.push(e.to);
88	}
89	}
90	}
91	return vis; // vis[v]=1 if v in S-side; else T-side
92	}
93	};
94
95	int main() {
96	ios::sync_with_stdio(false);
97	cin.tie(nullptr);
98
99	// Example: small graph
100	// 0(s) -> 1 (10), 0 -> 2 (5), 1 -> 2 (15), 1 -> 3 (10), 2 -> 4 (10), 3 -> 4 (10), 4(t)=5? We'll use 5 nodes with t=4.
101	int n = 5;
102	int s = 0, t = 4;
103	Dinic D(n);
104	D.set_source_sink(s, t);
105
106	D.add_edge(0, 1, 10);
107	D.add_edge(0, 2, 5);
108	D.add_edge(1, 2, 15);
109	D.add_edge(1, 3, 10);
110	D.add_edge(2, 4, 10);
111	D.add_edge(3, 4, 10);
112
113	long long ans = D.max_flow();
114	cout << "Max flow = " << ans << "\n";
115
116	auto S = D.min_cut_side_S();
117	cout << "Min-cut edges (S->T):\n";
118	for (int u = 0; u < n; ++u) if (S[u]) {
119	for (auto &e : D.adj[u]) {
120	// If e is a forward residual edge now (cap may be < original), we can't easily know original capacity without storing it.
121	// For demonstration, print edges that cross from S to non-S and currently have zero residual cap on forward edge (likely saturated in min-cut).
122	if (!S[e.to]) {
123	cout << u << " -> " << e.to << " (residual cap now = " << e.cap << ")\n";
124	}
125	}
126	}
127	return 0;
128	}
129