PROBLEM LINK:DIFFICULTYHARD PREREQUISITESGraph Theory, All Pair Shortest Paths, Minimum Cost Flow, Binary Search PROBLEMYou are given a directed graph G of cities. You select some paths on the graph, and cost is calculated as follows
EXPLANATIONFirst, let us make the problem easier. In the original problem a city can be visited by more than one hero and may be visited by the same hero more than once. We wish to simulate paths of heroes that might be using the same set of edges to connect different cities; at the same time making sure that we don't accidentally start marking some cities that would have been visited as unvisited. We augment G by adding edges between all pairs of vertices; the cost of these edges is equal to the cost of the minimum cost paths between the vertices. Two heroes may now traverse along these paths. We apply the restriction that two heroes must visit mutually exclusive cities. We can easily see that any configuration of paths with mutually exclusive vertices in this new graph will correspond to a valid path traversal in the original graph. Note that although there exists a single edge between each pair of vertices of the smallest weight, we will be using minimum cost maximum flow algorithm to ensure that we mark as many cities that can be marked as visited by the hero to reduce paying redundant "C" for cities that remain unvisited. Now, the problem reduces to finding a min cost path cover of the graph.
The min cost path cover can be found by using a reasonably efficient Minimum Cost Maximum Flow algorithm on the graph T, such that
A minimum cost maximum flow will be the minimum cost path cover in G. You can verify this intuitively by trying it on a small example. Now after k successful augmentations, we will have a graph T in which we are routing k units of flow through T. That means, we would have matched k vertices from A to k vertices from B. For vertices that are not yet matched in B, we note that
Thus, we want to keep adding a unit of flow one by one. Let c[k] be the cost of introducing the k^{th} unit of flow. If c[k] is larger than C, then we know it is better to compensate the cities than to introduce another hero. The problem is that doing this one by one might be too slow (since k can be as large as n). But we also know that the marginal cost of each unit of flow is larger than the previous unit of flow. Formally, Hence we can precalculate the array c (and the cumulative sums of prefix of c, called cc), and then given C we can binary search on c to find from which unit of flow onwards, is it better to compensate instead of add new flow (or heroes). If such a point comes out to be i, then the answer is The overall algorithm looks like
SETTERS SOLUTIONCan be found here TESTERS SOLUTIONCan be found here ACKNOWLEDGEMENTI owe cgy4ever for having written such an amazing writeup explaining his solution to the problem. The entire editorial is mostly copy pasted from his ideas! You can view his writeup here.
This question is marked "community wiki".
asked 11 Sep '12, 15:31

I got as far as reducing to mincost bipartite matching (essentially the same as what is described here as a flow), but I didn't figure out that clever way to avoid having to do so much work for each different value of C (I had extra edges in the graph with cost C, which made it harder to see for me, I guess).
Nice solution!