Cost-Optimized Directed Flow — Problem Statement & Solution Guide
Problem Description
You are given a directed graph with $N$ vertices labeled from $1$ to $N$ and $M$ directed edges. Each edge is described by a triple $(u,v,c)$ meaning a directed connection from vertex $u$ to vertex $v$ that can carry at most $c$ units of flow. Two distinct vertices, the source $s$ and the sink $t$, are also specified. Your task is to compute the maximum amount of flow that can be sent from $s$ to $t$ without exceeding any edge’s capacity.
The flow must satisfy the usual conservation constraints: for every vertex other than $s$ and $t$, the total incoming flow must equal the total outgoing flow. The objective is to maximize the total flow leaving $s$ (which equals the total flow entering $t$). The graph may contain parallel edges and cycles, but all capacities are non‑negative integers.
Input format:
- The first line contains two integers $N$ and $M$.
- The next $M$ lines each contain three integers $u$, $v$, and $c$ describing an edge.
- The last line contains two integers $s$ and $t$.
Output format:
- A single integer: the maximum flow value from $s$ to $t$.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Cost-Optimized Directed Flow"
WHY DOES IT MATTER?
Maximum flow is a cornerstone of network optimization, appearing in logistics, bandwidth allocation, and bipartite matching; mastering it equips engineers to model and solve resource‑constrained routing problems efficiently.
OPTIMIZATION CHALLENGE
The key insight is to avoid recomputing paths from scratch after each augmentation; by using BFS to find the shortest augmenting path (Edmonds‑Karp) or building a level graph and sending blocking flows (Dinic), we bound the number of augmentations and achieve polynomial time.
REAL-WORLD CONNECTION
Think of a water distribution system where pipes have limited capacity; the max‑flow algorithm determines the most water you can push from a reservoir (source) to a city (sink) without over‑pressurizing any pipe, mirroring load‑balancing in distributed services.
In an interview, implement Edmonds‑Karp first because it’s simpler and deterministic; keep the residual graph as adjacency lists of edge objects with reverse pointers to update capacities in O(1) per augmentation.
COMPLEXITY AT A GLANCE
O(V * E^2)O(V + E)Core Theory — Why This Approach?
The maximum flow problem on a directed graph asks for the greatest amount of material that can travel from a designated source vertex s to a sink vertex t without exceeding the capacity c of any edge. The classic solution relies on the residual network concept: for each edge we keep track of remaining capacity and introduce a reverse edge that allows flow to be cancelled. Augmenting paths—paths from s to t in the residual graph—represent opportunities to push additional flow. By repeatedly finding such paths and augmenting along the bottleneck edge, the algorithm converges to a flow where no augmenting path exists, which by the Max‑Flow Min‑Cut theorem is optimal.
A naïve approach that enumerates all possible s‑t paths and tries every combination of flow assignments quickly becomes infeasible because the number of simple paths can be exponential in N and M. Moreover, without a systematic way to update capacities, the algorithm may revisit the same edges many times, leading to O(2^N) or worse runtime. The optimal paradigm—Edmonds‑Karp (BFS‑based) or Dinic’s algorithm (level graph + blocking flow)—structures the search for augmenting paths, guaranteeing polynomial time. Edmonds‑Karp runs in O(V·E^2) by always picking the shortest‑in‑edges augmenting path, while Dinic improves to O(E·V^2) and O(E·√V) on unit‑capacity graphs, making them suitable for the medium‑difficulty constraints typical of coding interviews.
Interview Questions on This Problem
Q1How does the Max‑Flow Min‑Cut theorem justify that a flow with no augmenting path is optimal?
The theorem states that the value of the maximum flow equals the capacity of the minimum s‑t cut. When no augmenting path exists in the residual graph, the set of vertices reachable from s defines a cut whose forward edges are saturated and backward edges have zero flow, meaning the flow value equals the cut capacity, proving optimality.
Q2When would you prefer Dinic’s algorithm over Edmonds‑Karp for a given graph?
Dinic’s algorithm excels on dense graphs or graphs with many parallel edges because it processes multiple augmenting paths in a single BFS‑derived level graph, achieving O(E·V^2) versus Edmonds‑Karp’s O(V·E^2). It also performs better on unit‑capacity or bipartite matching scenarios where its O(E·√V) bound applies.
Q3Explain how you would modify the max‑flow algorithm to handle edges with lower bounds on flow.
Introduce a transformation: for each edge (u,v) with lower bound l and capacity c, subtract l from c, add a demand of l to v and a supply of l to u, then add a super‑source and super‑sink connecting all supply/demand nodes. Run a standard max‑flow; if the flow saturates all added edges, a feasible flow respecting lower bounds exists.
Examples
Input
4 5 1 2 3 1 3 2 2 3 1 2 4 2 3 4 4 1 4
Output
5
Explanation: The optimal flow uses the following paths: 1) 1→2→4 with capacity 2. 2) 1→2→3→4 with capacity 1. 3) 1→3→4 with capacity 2. Total flow = 2+1+2 = 5, which is the maximum possible.
Input
3 3 1 2 5 2 3 3 1 3 4 1 3
Output
7
Explanation: Send 4 units directly along 1→3. Send 3 units along 1→2→3. No other augmenting paths exist, so the maximum flow is 4+3 = 7.
Input
5 7 1 2 10 1 3 5 2 4 10 3 4 5 4 5 15 2 3 2 3 2 2 1 5
Output
15
Explanation: All capacity from 1→2 and 1→3 can reach 5 via 4→5. The edge 4→5 has capacity 15, which is sufficient for the 10 units from 1→2→4 and the 5 units from 1→3→4. Thus the maximum flow equals 10+5 = 15.
Constraints
- 2 <= N <= 500
- 1 <= M <= N*(N-1)
- 1 <= c <= 10^6
- s != t
- All vertices are labeled from 1 to N
Optimal Approach & Strategy
Use Edmonds‑Karp: repeatedly run BFS on the residual graph to find the shortest augmenting path and push flow along it until no such path remains.
Brute Force Approach
Enumerate every simple s‑t path, try all possible flow distributions across those paths, and keep the best feasible total.
Verified Code Solutions
function solution(graph, flow, source, sink) {
let residualGraph = JSON.parse(JSON.stringify(graph));
let maxFlow = 0;
while (true) {
let parent = new Array(Object.keys(graph).length).fill(-1);
let queue = [source];
while (queue.length > 0) {
let u = queue.shift();
for (let v in residualGraph[u]) {
if (residualGraph[u][v] > 0 && parent[v] === -1) {
parent[v] = u;
queue.push(v);
}
}
}
if (parent[sink] === -1) break;
let pathFlow = Infinity;
let v = sink;
while (v !== source) {
let u = parent[v];
pathFlow = Math.min(pathFlow, residualGraph[u][v]);
v = u;
}
maxFlow += pathFlow;
v = sink;
while (v !== source) {
let u = parent[v];
residualGraph[u][v] -= pathFlow;
residualGraph[v][u] = (residualGraph[v][u] || 0) + pathFlow;
v = u;
}
}
return maxFlow;
}class Solution {
public:
int solution(vector<vector<int>>& graph, int flow, int source, int sink) {
vector<vector<int>> residualGraph = graph;
int maxFlow = 0;
while (true) {
vector<int> parent(graph.size(), -1);
queue<int> queue;
queue.push(source);
while (!queue.empty()) {
int u = queue.front();
queue.pop();
for (int v = 0; v < graph.size(); v++) {
if (residualGraph[u][v] > 0 && parent[v] == -1) {
parent[v] = u;
queue.push(v);
}
}
}
if (parent[sink] == -1) break;
int pathFlow = INT_MAX;
int v = sink;
while (v != source) {
int u = parent[v];
pathFlow = min(pathFlow, residualGraph[u][v]);
v = u;
}
maxFlow += pathFlow;
v = sink;
while (v != source) {
int u = parent[v];
residualGraph[u][v] -= pathFlow;
residualGraph[v][u] = (residualGraph[v][u] == 0) ? pathFlow : residualGraph[v][u] + pathFlow;
v = u;
}
}
return maxFlow;
}
};class Solution {
public int solution(int[][] graph, int flow, int source, int sink) {
int[][] residualGraph = graph.clone();
int maxFlow = 0;
while (true) {
int[] parent = new int[graph.length];
java.util.Queue<Integer> queue = new java.util.LinkedList<>();
queue.add(source);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < graph.length; v++) {
if (residualGraph[u][v] > 0 && parent[v] == -1) {
parent[v] = u;
queue.add(v);
}
}
}
if (parent[sink] == -1) break;
int pathFlow = Integer.MAX_VALUE;
int v = sink;
while (v != source) {
int u = parent[v];
pathFlow = Math.min(pathFlow, residualGraph[u][v]);
v = u;
}
maxFlow += pathFlow;
v = sink;
while (v != source) {
int u = parent[v];
residualGraph[u][v] -= pathFlow;
residualGraph[v][u] = (residualGraph[v][u] == 0) ? pathFlow : residualGraph[v][u] + pathFlow;
v = u;
}
}
return maxFlow;
}
}def solution(graph, flow, source, sink):
residual_graph = {k: v.copy() for k, v in graph.items()}
max_flow = 0
while True:
parent = [-1] * len(graph)
queue = [source]
while queue:
u = queue.pop(0)
for v in residual_graph[u]:
if residual_graph[u][v] > 0 and parent[v] == -1:
parent[v] = u
queue.append(v)
if parent[sink] == -1:
break
path_flow = float('inf')
v = sink
while v != source:
u = parent[v]
path_flow = min(path_flow, residual_graph[u][v])
v = u
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
residual_graph[u][v] -= path_flow
residual_graph[v][u] = (residual_graph[v][u] or 0) + path_flow
v = u
return max_flowfunction solution(graph, flow, source, sink) {
let residualGraph = JSON.parse(JSON.stringify(graph));
let maxFlow = 0;
while (true) {
let parent = new Array(Object.keys(graph).length).fill(-1);
let queue = [source];
while (queue.length > 0) {
let u = queue.shift();
for (let v in residualGraph[u]) {
if (residualGraph[u][v] > 0 && parent[v] === -1) {
parent[v] = u;
queue.push(v);
}
}
}
if (parent[sink] === -1) break;
let pathFlow = Infinity;
let v = sink;
while (v !== source) {
let u = parent[v];
pathFlow = Math.min(pathFlow, residualGraph[u][v]);
v = u;
}
maxFlow += pathFlow;
v = sink;
while (v !== source) {
let u = parent[v];
residualGraph[u][v] -= pathFlow;
residualGraph[v][u] = (residualGraph[v][u] || 0) + pathFlow;
v = u;
}
}
return maxFlow;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.