UVa 908

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

Summary[edit]

Given a set of N edges of a tree, output the total cost of this tree. Then given another set of K+M edges, construct an MST using these edges and output its cost.

Gotchas[edit]

Just a naive MST constructing problem. Nothing special to consider

Notes[edit]

  • In the problem statement, N may be as large as 1,000,000, and 1<=M<= N*(N-1)/2, which is large than 2^32.

But the data sets is seem to be so weak that such an M does not exist, which means that using int is enough.

By the way, do not print a blank line after the last test case.

Input[edit]

5
1 2 5
1 3 5
1 4 5
1 5 5
1
2 3 2
6
1 2 5
1 3 5
1 4 5
1 5 5
3 4 8
4 5 8

4
1 2 5
1 3 5
1 4 5
1
2 3 2
4
1 2 5
1 3 5
1 4 5
3 4 8

Output[edit]

20
17

15
12

References[edit]