Secret Pipes (solution through graphs)

USACO Open 2002, Green Division

The task

Farmer John wants to organize his water distribution system as cheaply as possible, but he does not want his rival Farmer Pluto to predict the routes he chooses. Farmer John knows that such a task usually requires the cheapest method of pipe laying, so he decided to use the second most expensive method.

A list of all bidirectional pipes that can connect multiple W (3 <= W <= 2,000) water stations (each of which can be built into a well) is given. Your task is to find the second of the cheapest ways to connect pumping stations using no more than P (P <= 20,000) pipes with a given cost of each pipe. There should be no pipe connecting the station with itself. There should not be two pipes connecting the same pair of stations twice. It is guaranteed that there is only one cheapest way to distribute water, and that there are at least two ways to distribute water. All values ​​are positive numbers that fit into a 32-bit integer. A water station is identified by its number - an integer in the range l..W.

Input

line 1 - two space-separated integers, W u P;
lines 2..P + 1 - each line describes one pipe and contains 3 numbers, separated by a space, the station numbers of the beginning and end of the pipe, as well as the cost of this pipe.

Conclusion

One line containing an integer - the second minimum cost of constructing a water distribution system.

  Input example: Output example:
 5 7 20
 1 2 3 
 2 3 4 
 1 4 7 
 2 4 11 
 2 5 9 
 5 4 5 
 3 5 8 

Solution [up]

In this problem, we can consider pumping stations as vertices; the pipes connecting the pumping stations are like ribs, and the cost of the pipes is like the weights of the ribs. Then, by the condition of the problem, we are required to build a second spanning tree by weight.

Now the solution of the problem can be provided as follows.
1. Find the minimum spanning tree.
2. "Removing" one of the found edges of the minimum spanning tree in a cycle in turn and completing the remaining incomplete skeleton to the minimum spanning tree, we calculate the cost of the resulting trees and remember the smaller one.

To find the minimum spanning tree, we use the Kruskal algorithm.

Formal description [up]

  Pipes ()
 1. Read the list of graph edges from a file.
 2. Sort the edges of the graph in ascending order of their weight (pipe prices).
 3. Use the Kruskal algorithm to find the smallest skeleton. 
    tree (perform paragraphs 3.1-3.3):
    3.1.  Initialize the length of the tree to 0.
    3.2.  Select the first edge of the graph in the list.
    3.3.  Until all edges of the graph have been viewed, repeat paragraphs.  3.3.1-3.3.3:
         3.3.1.  If the vertices of the current edge are not in the same component 
                connectivity, then add an edge to the smallest skeleton tree.
         3.3.2.  If the edge has been added, then add to the length of the tree 
                value of the weight of the added edge.
         3.3.3.  Go to the next edge.
 4. For each edge from the smallest skeleton tree, perform the subitems.  4.1.-4.2:
    4.1.  Find the minimum spar tree by the Kruskal algorithm, 
         not using the current edge.
    4.2.  If the constructed tree has a length less than the minimum for 
         skeleton tree, then consider this skeleton tree second in weight.
 5. Print the length of the second by weight spanner tree.