Bounty Hunter II
This problem asks us the minimum number of "people" required to visit every node in a DAG if they can start and finish at any node, only follow the appropriate edges, and not visit any previously visited node.
The key intuition is that for a given node, we only care where the person who visits us comes from, and where they go. If they come from "nowhere" we can consider that as taking the hit of using one extra person. Therefore the total cost is the number of planets for which the previous planet of their visitor is "none."
So we expand on that by splitting each node into an in and out node, and connected each out node to each appropriate in node. Consider the second sample input. The "out" nodes of 1 and 3 would be connected to the "in" node of 2, and the "out" node of 2 would be connected to the "in" nodes of 4 and 5. This represents that the person who visits 2 ultimately can come from 1 or 3, and the person who leaves 2 may do so towards 4 or 5. We have to add two further nodes, though, a "comes from nowhere" and "goes to nowhere" nodes. For instance, the people who visit 1 and 3 have to "come" from somewhere, and in this case, they come from nowhere. Similarly, the people who leave 4 and 5 have to "go" somewhere. Since any node can end up being an individuals first or last visited node in an optimal solution, each in node has an edge from the "came from nowhere" node, and each out node has an edge to the "went to nowhere node."
Now, we see we have a bipartite graph with the out nodes and the "comes from nowhere" node on the left, and the in nodes and the "goes to nowhere" node on the right. Further additions arise naturally. Since only 1 person can ever enter and exit each planet, we add an edge of weight 1 from the source to every out node on the left, and a similar edge from each in node to the sink. Since the "nowhere" nodes can have at most 'n' people (it will never take more than n people to visit n planets) we use that as their connections to the source and sink. Lastly, since we're not guaranteed to use all n of those people we have an edge of infinite weight connecting the two nowhere nodes.
If we ran max flow with simply this configuration, we would get exactly 2n as our flow each time (n going to the nowhere node on the left, and then to each in node on the right, and 1 each to the out nodes on the left, culminating in n coming out of the nowhere node on the right). This is unhelpful. What we need is some way to prioritize NOT using the "comes from nowhere" node for everything, because as we said, we can ALWAYS just use n people for n planets.
The solution comes in the form of of assigning costs to each edge. In this case, we want to the cost of moving from one planet to cost nothing (since it doesn't use a new person), and the cost of taking a person from "nowhere" to cost something (since this means using an extra person). In this case, we say moving from the nowhere node to any planet costs 1, and moving from any planet to another, to the "nowhere" node, or from the nowhere node to the other nowhere node costs nothing.
We can now run min-cost-max-flow against our graph, and the following guarantees will be met:
- someone will LEAVE each node. At worst case, the person will go nowhere...but they will definitely leave
- someone will ARRIVE at each node. Again at worst case, they will come from nowhere incurring a cost, but they will definitely arrive
- not more than 1 person will arrive and leave each node. The edges connecting each node to the source/sink guarantee that
- for the given flow as few people as possible will move from nowhere to a planet, since that is the only thing that incurs a cost.
That's it. run min-cost-max-flow against the transformed graph. This is the identical transformation to what is used in Catering.