PROBLEM LINK:
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Max Flow
EXPLANATION:
We Can Build a Flow network Graph in the following manner.
Take a source and a sink.
Then make N nodes, one for each Type of Coin , and Build T more nodes, one for each merchant. One edge with capacity 1 is added between each one of the N nodes toward the sink. One edge with capacity Ci is added between the source toward each one of the N nodes. Ci is how many coins belongs to that Type at the beginning.
Now let’s Understand the process of changing coin’s Types.
Each merchant is able to take a set of coins belonging to some Types, that he can convert, but at most one per Type, then each coin will get converted and change its Type (Not necessary will change his Type).
This can be achieved in following Manner.
Let’s add one edge with capacity 1 between each Type toward all the merchants who are able to convert this Type.
Another edge with capacity 1, is needed to be added, between each merchant and all the Types he can convert coins to.
Finally , The max flow value of this Complete network is our answer .
SOLUTION:
To be Updated Soon