## 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 nodes, representing the source, sink, cities, and roads. The idea is to have edges with capacity from the source to the roads, and edges with capacity from the cities to the sink. Suppose is the set of vertices of a cut including the source. The cost of the cut is the sum of for roads not in , and for cities in . So, 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 nodes and arcs.

#### Solution 2

Let be the set of edges with both ends in . Then the net profit for a set of vertices is . However, note the following equation:

So, the answer can be written as

Or equivalently, as

where .

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 is positive or negative.

The resulting flow construction has nodes and edges.

## Comments

There are no comments at the moment.