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:
- one source vertex,
- M vertices, each vertex corresponds to a voucher in Karl’s wallet,
- n vertices, each vertex corresponds to an item in Karl’s shopping cart,
- one sink vertex
and the following edges:
- Edges from source to vertices corresponding to vouchers. Capacity of an edge going from source to
a vertex corresponding to i-th voucher is the value of that voucher.
- Edges from voucher vertices to item vertices. An edge going from a vertex corresponding to i-th
voucher to vertex corresponding to j-th item exists and has inifinite capacity if and only if i-th
voucher can be used to pay for j-th item.
- Edges from item vertices to sink. Capacity of an edge going from a vertex corresponding to i-th
item is the price of that item.
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.
