Kingdom of Tree
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3 Accepted Submission(s): 1
Special Judge
Problem Description
The Kingdom of Tree has $N$ cities numbered from 1 to $N$. The $N$ cities are connected by $N-1$ roads, and any two cities are reachable via a sequence of roads. Obviously, the road system of the Kingdom of Tree is constructed according to a tree structure. That¡¯s how the kingdom¡¯s name comes.
To monitor and protect the roads, the general of the kingdom decides to build radar stations in the cities. We denote the radius of the radar station located in city $i$ as $R_i$. $R_i$ is a non-negative integer, and $R_i=0$ indicates that there is no radar station in city $i$. Given a road connecting city $i$ and city $j$, whose length is denoted as $L_{i,j}$, we say that the road is monitored by radar if $R_i+R_j¡ÝL_{i,j}$.
The cost of building a radar station in city $i$ is proportional to its radius $R_i$. Given a construction plan of the radar stations $P=\{R_1,R_2,...,R_N \}$, we denote the set of monitored roads as S. The cost per length is thus defined as the ratio between the sum of $R_i$ and the sum of the length of monitored roads: $\sum_{i=1}^{N} R_{i}/\sum_{(i,j)¡ÊS}L_{i,j}$.
Due to limited budget, the general wants to make the most of the money. He wants a construction plan that minimizes the cost per length. Note that he don¡¯t have to monitor all the roads. As the most brilliant programmer of the Kingdom of Tree, can you help him to find such a construction plan?
To monitor and protect the roads, the general of the kingdom decides to build radar stations in the cities. We denote the radius of the radar station located in city $i$ as $R_i$. $R_i$ is a non-negative integer, and $R_i=0$ indicates that there is no radar station in city $i$. Given a road connecting city $i$ and city $j$, whose length is denoted as $L_{i,j}$, we say that the road is monitored by radar if $R_i+R_j¡ÝL_{i,j}$.
The cost of building a radar station in city $i$ is proportional to its radius $R_i$. Given a construction plan of the radar stations $P=\{R_1,R_2,...,R_N \}$, we denote the set of monitored roads as S. The cost per length is thus defined as the ratio between the sum of $R_i$ and the sum of the length of monitored roads: $\sum_{i=1}^{N} R_{i}/\sum_{(i,j)¡ÊS}L_{i,j}$.
Due to limited budget, the general wants to make the most of the money. He wants a construction plan that minimizes the cost per length. Note that he don¡¯t have to monitor all the roads. As the most brilliant programmer of the Kingdom of Tree, can you help him to find such a construction plan?
Input
The first line of input contains a number $T$ indicating the number of test cases ($T¡Ü200$).
Each test case starts with a line containing an integer $N$ indicating the number of cities ($2¡ÜN¡Ü30$). Each of the next $N-1$ lines contains three integers $i, j$, and $k$, indicating that there is a road between city $i$ and city $j$, and its length is $k$. ($1¡Üi¡Ùj¡ÜN,1¡Ük¡Ü10^9$ )
It is guaranteed that any two cities are reachable via a sequence of roads.
Each test case starts with a line containing an integer $N$ indicating the number of cities ($2¡ÜN¡Ü30$). Each of the next $N-1$ lines contains three integers $i, j$, and $k$, indicating that there is a road between city $i$ and city $j$, and its length is $k$. ($1¡Üi¡Ùj¡ÜN,1¡Ük¡Ü10^9$ )
It is guaranteed that any two cities are reachable via a sequence of roads.
Output
For each test case, output a single line consisting of ¡°Case #X: Y¡±. $X$ is the test case number starting from 1. $Y$ is the minimum cost per length. You answer is considered correct if its absolute error is less than $10^{-6}$.
Sample Input
4 7 1 2 1 2 3 2 3 4 99 4 5 3 5 6 1 6 7 4 4 1 2 3 2 3 2 2 4 1 5 1 2 2 2 3 1 3 4 2 3 5 5 2 1 2 3
Sample Output
Case #1: 0.66666667 Case #2: 0.50000000 Case #3: 0.62500000 Case #4: 1.00000000