MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A distribution network has two depots s1,s2s_1,s_2 and two stores t1,t2t_1,t_2, linked through two warehouses a,ba,b with capacities c(s1,a)=5c(s_1,a)=5, c(s1,b)=3c(s_1,b)=3, c(s2,a)=2c(s_2,a)=2, c(s2,b)=6c(s_2,b)=6, c(a,t1)=4c(a,t_1)=4, c(a,t2)=3c(a,t_2)=3, c(b,t1)=3c(b,t_1)=3, c(b,t2)=5c(b,t_2)=5 (each depot can ship as much as its own arcs allow). What is the maximum total amount of goods that can reach the two stores combined?