Maximum Flow (Edmonds-Karp)
HardGraphBFSLinked List
Description
Given a directed weighted graph with n nodes (0..n-1) and a list of directed capacity edges [u, v, c], return the maximum flow from source 0 to sink n-1.
Examples
Input:
n = 4, edges = [[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,3]]Output:
5Explanation:
Running BFS-based augmenting paths yields a standard maximum flow of 5 from node 0 to node 3.
Input:
n = 2, edges = [[0,1,10]]Output:
10Explanation:
A single edge of capacity 10 between source and sink supports a maximum flow of 10.
Input:
n = 3, edges = [[0,1,5],[1,2,5]]Output:
5Explanation:
Series capacities of 5 and 5 form a bottleneck of 5 from source to sink.
Constraints
- •
2 ≤ n ≤ 50 - •
1 ≤ capacity ≤ 1000