MathCastle
Graph TheoryMediumDirected Graphs and Network Flows

Directed Graphs and Network Flows · Medium problem

A flow network has source ss, sink tt, and vertices a,b,ca,b,c, with capacities c(s,a)=6c(s,a)=6, c(s,b)=4c(s,b)=4, c(a,b)=2c(a,b)=2, c(a,c)=4c(a,c)=4, c(b,c)=3c(b,c)=3, c(b,t)=3c(b,t)=3, c(c,t)=6c(c,t)=6. It already carries a flow of value 33, sending 33 units along s→a→c→ts\to a\to c\to t and nothing else. Using the still-untouched path s→b→c→ts\to b\to c\to t, push its bottleneck. What is the flow's new total value?