Felix Halim .NET  
University Experience
IOI 2002 Yong In, Korea
ACM ICPC Regional Manila 2003
ACM ICPC Regional Manila 2004
ACM ICPC Regional Manila 2005
ACM ICPC Regional Kaohsiung 2006
ACM ICPC Regional Singapore 2007
ACM ICPC Regional Jakarta 2008 (ext)
ACM ICPC Regional Jakarta 2009 (ext)
ACM ICPC Regional Jakarta 2010
ACM ICPC Regional Jakarta 2012  Problem H
ACM ICPC Regional Jakarta 2013  Problem J (new!)
ACM ICPC World Final Tokyo 2007
Google India Code Jam 2005
Google India Code Jam 2006
Indonesia National Contest 2007
Indonesia National Contest 2008
Indonesia National Contest 2010
Facebook Hacker Cup 2011


ACM/ICPC Indonesia National Contest 2007Problem HTree MedianTime Limit: 3sA tree is a connected graph containing no cycles. A vertex is called a median vertex if the total cost to reach all vertices is minimal. There could be more than one median vertex in a tree, that’s why we define median as the set of all median vertices. To find median in a tree with small number of vertices is fairly easy task as you can solve this by a simple brute force program. In the left figure, we can see a weighted tree with 5 vertices. The tree median is {B} because the total cost from vertex B to all other vertices is minimal. BA = 2 BD = 7 BC = 1 BE = 7 + 5 = 12 TOTAL = 2 + 1 + 7 + 12 = 22 What if the number of vertices is quite large? This might be a problem since brute force program cost too much time. Given a weighted tree with N vertices, output the total cost to reach all vertices from its median. InputInput consists of several cases. Each case begins with an integer n (1<= n <= 10,000) denoting the number of vertices in a tree. Each vertex is numbered from 0...n1. Each of the next n1 lines contains three integers: a, b, and w (1<= w <= 100), which means a and b is connected by an edge with weight w.Input is terminated when n is equal to 0. This input should not be processed. OutputFor each case, output a line containing the sum of cost of path to all other vertices from the tree median.Sample Input5 0 1 2 1 2 1 1 3 7 3 4 5 6 0 1 1 1 2 4 2 3 1 3 4 4 4 5 1 0 Sample Output22 21 Problem Setter: Suhendry Effendy Kembali ke pembahasan soal ini Lihat problem lain: 