Given several sellers and buyers, each seller has an amount of products, each buyer wants to buy several products from sellers. Some sellers can not transact with some buyers, if a buyer can not get enough products as he wants, the transaction will not succeed. If we know there is one strategy that can satisfy all buyers, how to find this strategy?
I draw a graph to illustrate the problem, this is just an example. The question wants you to provide a transaction strategy for each buyer so that all buyers can get enough products they want.
seller buyer example
I assume one buyer may buy multiple things from one seller. It is not hard to change it to one item.
This can be solved by maximum flow algorithm. Direct edges from buyer to their connected sellers. Assign capacity b_i for those edges. B_i is the amount the buyer needs. Add two nodes S,T. Add edges from S to all buyers. Assign capacity b_i to each of those edges. B_i is again the amount the buyer i needs. Add edges from every seller vertex to T. Assign capacity S_i to those edges. S_i is the amount the seller i has. Find the maximum flow from S to T. If it is equal to the sum of all buyers required amounts then there is a solution to the problem and it can be found by the amount of flow which goes through every edge from buyers to sellers (this is a follow up of integral flow theorem).
