img
Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2013
Frozen Rose-Heads
fr.c, fr.cpp, Fr.java
The winter is coming and all the experts are warning that it will be the coldest one in the last
hundred years. Freddy needs to make sure that his garden does not sustain any damage. One
of the most important tasks is to make sure that no water remains in his large watering system.
All the water comes from a central node and is distributed by pipes to neighboring nodes and so
on. Each node is either a sprinkler (rose head) with no outgoing pipe or an internal node with
one or more outgoing pipes leading to some other nodes. Every node has exactly one incoming
pipe, except for the central node which takes the water directly from a well and has no incoming
pipe. Every pipe has a valve that stops all the water going through the pipe. The valves are of
different quality and age, so some may be harder to close than others.
Freddy knows his valves well and has assigned a value to each pipe representing the amount of
effort needed to close the corresponding valve. He asks you to help him count the minimum
effort needed to close some valves so that no water goes to the sprinklers.
Input Specification
The input contains several test cases. Each test case starts with a line with two integers, the
number of nodes n (2 n 1 000), and the number of the central node c (1 c n). Each of
the next n - 1 lines represents one pipe and contains three integers, u, v (1 u, v n) and w
(1 w 1 000), where u and v are the nodes connected by a pipe and w is the effort needed
to close the valve on that pipe. You may assume that every node is reachable from the central
node.
Output Specification
For each test case, output a single line containing the minimum sum of efforts of valves to be
closed, such that the central node gets separated from all sprinklers.
Sample Input
Output for Sample Input
3
1
9
2
1
5
5
1
3
4
7
7
7
6
10
7
5
10
6
4
1
6
3
1
5
2
1
5
1
2
This problem was adapted from Stanford Local Contest