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)=8c(s,a)=8, c(s,b)=5c(s,b)=5, c(a,b)=1c(a,b)=1, c(a,c)=6c(a,c)=6, c(b,c)=4c(b,c)=4, c(b,t)=2c(b,t)=2, c(c,t)=9c(c,t)=9. A flow sends f(s,a)=6f(s,a)=6, f(s,b)=5f(s,b)=5, f(a,b)=1f(a,b)=1, f(b,t)=2f(b,t)=2, with f(a,c)f(a,c) and f(b,c)f(b,c) left to satisfy conservation at aa and bb, and f(c,t)f(c,t) fixed to balance cc. What is the value of this flow?