UVa 10462

From Algorithmist
Jump to: navigation, search

10462 - Is There A Second Way Left ?[edit]

Summary[edit]

Given a weighted undirected graph, we have to find the second best Minimum Spanning Tree.

Explanation[edit]

  1. Run a Depth-First Search or Breadth-First Search to see if the graph is connected , if no then output no way
  2. Now find the Minimum Spanning Tree and mark all the edges which is part of the MST.
  3. 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.

Gotchas[edit]

  • MST must be connected

Notes[edit]

Input[edit]

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

Output[edit]

Case #1 : No second way
Case #2 : No way
Case #3 : 21
Case #4 : No second way