Instruction. a. You have 5 problems in this assignment. b. Submit your report (in PDF format) and source codes in a single compressed file "ID NAME_A2.zip" to iCampus (Do not include executable files). GCC compiler will be used to compile your source codes. Your program will get two arguments, input and output file names, from the command line as c. d. follows: 22 Your Executable INPUT FILE NAME OUTPUT FILE NAME e. Any work that you turn in should be your ot Problem #3. (Programming) Second MST (20 pts) Given a weighted undirected graph, provide the cost of the second minimum spanning tree. The second minimum spanning tree has the minimum cost except MSTs. In the figure, the left and right subfigures show the MST and the second MST, respectively. . i Input: In the first line, two integers n (1SnS 50,000) and m (1 sms 200,000) are given where n and m are the number of vertices and edges of the graph, respectively. The following lines describes m edges in a format of "a b c" indicating that the graph has an edge between vertices a and b with cost of c. Note that the vertex index begins with 1 and edge weights are positive. Output: You are required to output the cost of the second minimum spanning tree. You can output-1" if such tree does not exist Sample input Sample output 7 12 128 135 10 24 2 2518 3 4 3 3 6 16 45 12 4 6 30 47 14 574 6 7 26 Note that, your program ean allocate up to 512MB memory and should produce the output within 3 seconds. You are asked to briefly describe your algorithm in the report and name your source code file Instruction. a. You have 5 problems in this assignment. b. Submit your report (in PDF format) and source codes in a single compressed file "ID NAME_A2.zip" to iCampus (Do not include executable files). GCC compiler will be used to compile your source codes. Your program will get two arguments, input and output file names, from the command line as c. d. follows: 22 Your Executable INPUT FILE NAME OUTPUT FILE NAME e. Any work that you turn in should be your ot Problem #3. (Programming) Second MST (20 pts) Given a weighted undirected graph, provide the cost of the second minimum spanning tree. The second minimum spanning tree has the minimum cost except MSTs. In the figure, the left and right subfigures show the MST and the second MST, respectively. . i Input: In the first line, two integers n (1SnS 50,000) and m (1 sms 200,000) are given where n and m are the number of vertices and edges of the graph, respectively. The following lines describes m edges in a format of "a b c" indicating that the graph has an edge between vertices a and b with cost of c. Note that the vertex index begins with 1 and edge weights are positive. Output: You are required to output the cost of the second minimum spanning tree. You can output-1" if such tree does not exist Sample input Sample output 7 12 128 135 10 24 2 2518 3 4 3 3 6 16 45 12 4 6 30 47 14 574 6 7 26 Note that, your program ean allocate up to 512MB memory and should produce the output within 3 seconds. You are asked to briefly describe your algorithm in the report and name your source code file
