MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

A distribution system has two depots s1,s2s_1,s_2 and two stores t1,t2t_1,t_2, linked through warehouses a,ba,b with capacities c(s1,a)=4c(s_1,a)=4, c(s1,b)=3c(s_1,b)=3, c(s2,a)=2c(s_2,a)=2, c(s2,b)=5c(s_2,b)=5, c(a,t1)=3c(a,t_1)=3, c(a,t2)=2c(a,t_2)=2, c(b,t1)=3c(b,t_1)=3, c(b,t2)=2c(b,t_2)=2. Warehouse bb can additionally handle at most 44 units in total (regardless of how its individual links are used), while aa has no such extra limit. What is the maximum total amount that can reach the two stores combined?