Hi All, i'm trying to solve a problem that remembers knapsack, but a little bit difficult. Can someone help me please? :)
The problem is the following,
There is a diamond mine unexplored. This mine has the shape of a tree.
Each vertex of this tree is a collect point of diamonds, where it is possible to collect X diamonds.
The mine is obstructed. Because of that, we need to dig thru some vertices to reach a collect point of diamonds. There is a cost to dig between to vertices.
You can spend B money units digging the mine, and you want to collect the maximum of diamonds as possible.
Its important to notice that, once dug, you don't need to pay again to pass in an edge.
The picture below shows an example.
The first picture is the answer for a budget of 400 money units. The second one is the answer for a budget of 450 money units.
[Input] In the first line, the number of diamond collect points N (10≤N≤1,000) and total mining budget (0≤B≤10,000) are given.
In the next N lines, route information (start point, end point), mining cost and benefit of diamonds at the end of the point are given.
All numbers are natural number and they are separated by a space. The mine entrance number is always 0.
Full text and comments »