A group of traders are leaving Switzerland, and need to convert their Francs into various international currencies. There are n traders t1; t2; :::; tn and m currencies c1; c2; :::; cm. Trader tk has Fk Francs to convert. For each currency cj , the bank can convert at most Bj Franks to cj . Trader tk is willing to trade as much as Skj of his Francs for currency cj.(For example, a trader with 1000 Francs might be willing to convert up to 200 of his Francs for USD, up to 500 of his Francs for Japanese's Yen, and up to 200 of his Francs for Euros). Assuming that all traders give their requests to the bank at the same time, design an algorithm that the bank can use to satisfy the requests (if it is possible). 1. Describe how to construct a flow network.
2. Make a claim. Something like "this problem has a feasible solution if and only if the max flow is ..."
3. Prove the above claim in both directions.