631 . Disjoint Paths

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description


Path in a graph is defined to be disjoint if there is no common edge and vertex that belongs to more than one path. Given a connected graph with N
nodes and N - 1

weighted edges, we are interested in finding a set of up to K
paths in the graph which are disjoint to each other. The set of paths should be chosen so that the sum of all weight of edges of the paths is the maximum possible.



<!-- MATH
$\epsfbox{p4141.eps}$
-->
WIDTH="882" HEIGHT="401" ALIGN="BOTTOM" BORDER="0"
SRC="/ntujudge/problemdata/631.jpg"
ALT="\epsfbox{p4141.eps}">


The example above shows two configurations of disjoint paths in the same graph. When the limit of paths to be drawn (K

) is one (shown on the left), the maximum sum of all the weight of its edges is 13 (5+2+6). However, when we are allowed to draw up to 2 disjoint paths, we can draw two paths whose sum of edge weights evaluates to 15 (shown on the right).

Input Format


The input begins with a line containing an integer T
, the number of test cases follow. Each case begins with two non-negative integers N
and K

<!-- MATH
$(K \le N \le 60)$
-->
(K WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/631-2.png"
ALT="$ \le$">N WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/631-2.png"
ALT="$ \le$">60)
. The next N - 1
following lines each will contains three integers: A
, B

and D
(<!-- MATH
$1 \le A, B \le N$
-->
1 WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/631-2.png"
ALT="$ \le$">A, B WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/631-2.png"
ALT="$ \le$">N
; and <!-- MATH
$|D| \le 10000$
-->
| D| WIDTH="18" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
SRC="/ntujudge/problemdata/631-2.png"
ALT="$ \le$">10000

) which means that there is an undirected edge from node A
to node B
with weight D
.

Output Format


For each case, print in a single line the maximum possible sum of weight of up to K
disjoint paths in the given graph.

Sample Input 1



2 

6 1 

1 2 5

3 2 2

3 4 6

6 3 3

2 5 1

6 2 

1 2 5

3 2 2

3 4 6

6 3 3

2 5 1



Sample Output 1



13 

15



Hints

Problem Source

Migrated from old NTUJ.

ACM ICPC regional Jakarta site 2008

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 2000
Submit
Back to Top