Editorial for DMOPC '20 Contest 7 P5 - Mayors and Tolls


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Eliden

This problem can be solved with min cut / max flow. There are two main approaches:

Solution 1

Our construction has N+M+2 nodes, representing the source, sink, cities, and roads. The idea is to have edges with capacity p from the source to the roads, and edges with capacity b from the cities to the sink. Suppose S is the set of vertices of a cut including the source. The cost of the cut \delta(S) is the sum of p for roads not in S, and b for cities in S. So, S corresponds to a choice of cities to pay and roads to profit from.

By adding infinite-capacity edges from the roads to the incident cities, the minimum cut problem now has the constraints that for every profit we profit from, we must pay both incident cities.

So, the answer can be determined after finding the min cut / max flow for this network with \mathcal O(N+M) nodes and arcs.

Solution 2

Let E(S) be the set of edges with both ends in S. Then the net profit for a set of vertices S is p(E(S))-b(S). However, note the following equation:

\displaystyle p(E(S)) = \frac 1 2 \left(\sum_{v \in S} p(\delta(v))-p(\delta(S))\right)

So, the answer can be written as

\displaystyle \max_{S \subseteq V} \left(-\frac 1 2 p(\delta(S))+\sum_{v \in S} \left(\frac 1 2 p(\delta(v))-b_v\right)\right)

Or equivalently, as

\displaystyle \min_{S \subseteq V} \left(\frac 1 2 p(\delta(S))+\sum_{v \in S} b'_v\right)

where b'_v = b_v - \frac 1 2 p(\delta(v)).

This is very close to a minimum cut problem. To turn it into one, we add a source and sink and add an arc to every node to either the source or sink depending on whether b'_v is positive or negative.

The resulting flow construction has N+2 nodes and \mathcal O(N+M) edges.


Comments

There are no comments at the moment.