MST - Minimum Spanning Tree
Find the minimum spanning tree of the graph.
On the first line there will be two integers N - the number of nodes and M - the number of edges. (1 <= N <= 10000), (1 <= M <= 100000)
M lines follow with three integers i j k on each line representing an edge between node i and j with weight k. The IDs of the nodes are between 1 and n inclusive. The weight of each edge will be <= 1000000.
Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.
Input: 4 5 1 2 10 2 3 15 1 3 5 4 2 2 4 3 40 Output: 17
Anyone getting exactly 81.82 as their score should use long long. Both Prim's (with heap) and Kruskal's pass in time.Last edit: 2012-10-09 11:20:42
hope to see more textbook problems like this one -- useful to test the efficiency of your implementation
@ Nicolas i quess WA ...
Last edit: 2012-03-30 11:48:26
A score of 100 means you have passed all the test data. In Partial problems, your score reflects the percentage of total correct answers your solution produced.
I looked at the best solutions and don't understand how to scoring is done for this problem.