Task DescriptionDiscussion (0)
Task :: Greedy Hydra
Hydra is some very greedy animal. A hydra has 9 heads when he is born, and many more new heads will come out when he grows up. Of course, some old heads will break off because of caducidy.

One day, a hydra with M heads finds a tree with N fruits on it. He is very delighted and wants to eat this tree instantly. Since he has M heads, he must divide these N fruit into M groups, each group contains at least 1 fruit, and each head will eat a group of fruits.

The biggest head among the M heads is named "Boss", it must eat neither more nor less than K fruits, and, in the nature of things, the biggest fruit included. These fruits are connected by N-1 branches, and there exists a path made up with branches between each pair of fruit.

If two fruit connected by a single branch is put in different groups, the corresponding two heads will break the branch and eat the two fruits, otherwise the corresponding head will eat the two fruits without breaking the branch. Eating branches is not very comfortable of course, so every branch has a weight of illness, and the weight of illness of this hydra is the sum of the weights of illness of all branches he has eaten.

Your task is to help the hydra to minimize his weight of illness.

The picture below is an example.

N=8,M=2,K=4.The bigger head eats 4 fruits(full points), the smaller head eats 4 fruits(empty points). The branch signed by a thin segment is eaten by the hydra.

The first line contains N(1<=N<=300), M(2<=M<=N), K(1<=K<=N), separated by single spaces. The N fruits are numbered 1..N, and the biggest fruit is always numbered 1. N-1 lines follow, each contains 3 integers i,j,k separated by spaces denoted that there is a branch between fruit i (1<=i<=N) and fruit j (1<=j<=N) and the weight of illness of this branch is k(0<=k<=100000).

Print the minimum weight of illness of the hydra. If we can't divide the fruit into M groups, output "-1"(without quotes).

8 2 4
1 2 20
1 3 4
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5


Submit Solution
Available Languages
Task info
Name:Greedy Hydra
Time:0.5 sec.
Memory:32 MB
AddedBy: hendrik
Source:Chinese National Olympiad in Informatics 2002
Task Ratings

4.6 (7 votes)

4.5 (8 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
ohhenrie 0.01 s.
zjsxzy 0.01 s.
robodobo 0.01 s.
simpleton 0.011 s.
kipoujr 0.015 s.
smu201111192 0.02 s.
mister 0.024 s.
Kusika 0.028 s.
vjudge4 0.044 s.
ivan90 0.046 s.
Solved By