Internet Problem Solving Contest

IPSC 2009

Solution to Problem K – Karl's shopping

This problem can be transformed into a problem of finding maximum flow in the following way:

We construct a graph with a following vertices:

and the following edges:

Clearly each flow in from source vertex to sink vertex in this graph corresponds to a way of (partial) payment of the items in Karl’s shopping cart by vouchers in his wallet. Additionaly to such a payment he needs to use (sum of prices of all items) minus (value of that flow) cash money to pay all his shopping. That means that in order to minimize the amount of cash money we have to maximize the flow through this graph. This can be done e.g. by Ford-Fulkerson algorithm.