MathCastle
Graph TheoryMediumDirected Graphs and Network Flows

Directed Graphs and Network Flows · Medium problem

A flow network has arcs s→as\to a (capacity 66), a→ba\to b (capacity 33), b→tb\to t (capacity 55), and a→ta\to t (capacity 44), all carrying no flow yet. First push the path s→a→b→ts\to a\to b\to t to its bottleneck. Then push the path s→a→ts\to a\to t to ITS bottleneck (using the remaining residual capacity of s→as\to a). What is the total flow value after both pushes?