Open-Pit Mining
This problem gives us a DAG of nodes, each with an associated value and asks us for the maximum value subset with the condition that if any node is chosen, any of its ancestor nodes must be as well.
First simplification is to just subtract cost from value for each node to only deal with a single number. There is no reason to deal with them separately.
We can make a couple more graph transformations that help simplify things without changing the solution
- We can draw an edge from every negative weight node to any of its descendant nodes with positive weight. It should be easy to see that this does not change the solution.
- Given (1), and that we will always dig up a a positive note if we have dug up all its ancestors, we can eliminate any edges emanating from positive nodes.
- Given (1), we can eliminate any edges which arrive AT a negative node. Since we will never dig up a negative node UNLESS we want to dig up one of its descendants.
Draw some example graphs to convince yourself that these transformations are correct. You will also note the transformed graph has a good property, it is bipartite! All the negative nodes are on one side, with no incoming edges, and all the positive nodes on the other, with no outgoing edges. From here, the guess is this might be maxflow related!
The intuitive understanding is that in order to choose a positive node, one must be able to "justify" the negative value of the nodes which are ancestors, and all the positive weight nodes must collectively be able to be "justified" by the set of negative weight nodes which are ancestors. This starts to sound a lot like a flow problem, which it is! We simply connect source node to each of the negative weight nodes with abs(value) as the cost, and the positive weight nodes to the sink with (value) as the cost, then connect the two sides with weight infinite. As we push flow across the graph, the minimum cut moves in such a way that one side of the cut will be "negative value" constrained set of nodes, and the other side of the cut will be "positive value" constrained set of nodes. Since the middle of the graph is all infinite weight, the minimum cut will never be there.
When max flow is run, the set of nodes which are "negative weight" constrained will be the ones which ultimately determine the max flow of the graph (aka the min-cut). Nodes on the source side of the cut will be in the final set (meaning the cut is beyond the negative weight nodes, and thus the set is negative weight constrained), and nodes on the sink side will cut will not be included. The problem only asks for the maximum flow, however.
There are 200 nodes, which means we run fast enough. Further, the count is also a good hint that the solution required a flow.