UVa 10462
From Algorithmist
Contents |
[edit] 10462 - Is There A Second Way Left ?
[edit] Summary
Given a weighted undirected graph, we have to find the second best Minimum Spanning Tree.
[edit] Explanation
- Run a Depth-First Search or Breadth-First Search to see if the graph is connected , if no then output no way
- Now find the Minimum Spanning Tree and mark all the edges which is part of the MST.
- Ignore the edges which are part of the MST, one at a time and try to build a new MST with the available edges (be careful that the MST must be connected).
- Find the weight of MST. Among all the connected MST's find the minimum weight which is the answer . If there is no connected MST , then output no second way..
Let us take an example, let there be 5 edges in a graph G labeled 1 to 5.
let the MST considering all the edges, consists of edges 1, 3, 5. now ignore edge 1 only and consider edge 2, 3, 4, 5 to build an MST if it is possible to build an mst calculate its weight now ignore edge 3 only do the same now ignore edge 5 only and do the same among all the MST's the minimum weight one is the second best MST.
[edit] Gotchas
- MST must be connected
[edit] Notes
- A similar problem is UVa 10600.
[edit] Input
4 5 4 1 2 5 3 2 5 4 2 5 5 4 5 5 3 1 2 5 3 2 5 5 4 5 5 5 1 2 5 3 2 5 4 2 5 5 4 5 4 5 6 1 0
[edit] Output
Case #1 : No second way Case #2 : No way Case #3 : 21 Case #4 : No second way
