Algorithms Chapter 7 Problem 20

7.20. Consider the following generalization of the maximum flow problem. You are given a directed network G = (V. E) with edge capacities (e). Instead of a single (s,t) pair, you are given multiple pairs (81,t), (82:, . . . , (sk, tk), where the si are sources of G and the ti are sinks of G. You are also given k demands d,... ,dk. The goal is to find k flows fa)flk) with the following properties: . f) is a valid flow from s, to t . For each edge e, the total flow fe 1) + f(2) + + fek) does not exceed the capacity Co. The size of each flow f is at least the demand d. The size of the total flow (the sum of the flows) is as large as possible. How would you solve this problem? 7.20. Consider the following generalization of the maximum flow problem. You are given a directed network G = (V. E) with edge capacities (e). Instead of a single (s,t) pair, you are given multiple pairs (81,t), (82:, . . . , (sk, tk), where the si are sources of G and the ti are sinks of G. You are also given k demands d,... ,dk. The goal is to find k flows fa)flk) with the following properties: . f) is a valid flow from s, to t . For each edge e, the total flow fe 1) + f(2) + + fek) does not exceed the capacity Co. The size of each flow f is at least the demand d. The size of the total flow (the sum of the flows) is as large as possible. How would you solve this