MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

A network has s,a,b,ts,a,b,t with capacities c(s,a)=3c(s,a)=3, c(s,b)=1c(s,b)=1, c(a,b)=3c(a,b)=3, c(a,t)=1c(a,t)=1, c(b,t)=3c(b,t)=3. Pushing the single path s→a→b→ts\to a\to b\to t first (to its own bottleneck) saturates every arc on it, after which NO path using only forward arcs remains from ss to tt. What is this network's actual maximum flow value?