UVa 10600

From Algorithmist
Jump to: navigation, search

10600 - ACM Contest and Blackout[edit]

Summary[edit]

Given a Graph, find the Minimum Spanning Tree and the second Minimum Spanning Tree.

Explanation[edit]

Find the Minimum Spanning Tree. (O(V^{2}) implementation is fine.) Since the Minimum Spanning Tree algorithm is a Greedy algorithm, one of the second Minimum Spanning Tree should have nearly the same structure, if we were not so greedy on the edges. Note that in the Minimum Spanning Tree, there are V-1edges. We can bruteforce this by removing the edges of the Minimum Spanning Tree one at a time, and calculating the resultant Minimum Spanning Tree. The one with the minimum cost would be the second Minimum Spanning Tree. The total complexity is O(V^{3}).

Input[edit]

3
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
4 4
1 4 5
1 2 2
2 3 3
1 3 4

Output[edit]

110 121
37 37
10 11