MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

A flow network has source ss, sink tt, and vertices a,b,c,da,b,c,d in between, with capacities c(s,a)=8c(s,a)=8, c(s,b)=5c(s,b)=5, c(a,b)=3c(a,b)=3, c(a,c)=6c(a,c)=6, c(b,d)=5c(b,d)=5, c(c,d)=2c(c,d)=2, c(c,t)=5c(c,t)=5, c(d,t)=7c(d,t)=7. Running Ford-Fulkerson from scratch, what is the maximum flow value from ss to tt?