MST - Minimum Spanning Tree
Find the minimum spanning tree of the graph.
Input
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.
Output
Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.
Example
Input: 4 5 1 2 10 2 3 15 1 3 5 4 2 2 4 3 40 Output: 17
hide comments
wxydth:
2022-08-25 14:48:51
You can use Boruvka's Algorithm |
|
soumak:
2021-04-26 06:57:01
What is 9.09?? |
|
shubho5das:
2021-02-23 20:23:33
Try implementing both Kruskal's as well as Prim's Last edit: 2021-03-09 13:22:19 |
|
ravi7526:
2021-02-11 12:21:23
what do mean by 9.09 error |
|
kya_bantai:
2020-11-11 06:55:37
try to implement both prims's and krushal's algorithm |
|
dodongchien123:
2020-09-12 15:59:28
This problem is another kind of judge. So 0 to 100 is your result, which 100 is fully passed (accepted). |
|
abhishek__2007:
2020-07-25 12:26:58
my code is based on DISJOINT SET UNION taking O(1)*m time but why i am not getting 100pts.is am getting TLE on some TC;
|
|
harsh_k:
2020-07-17 20:42:45
why is it showing 0 and not 100 as others have pointed. I think I solved it correctly as it shows green colour but still why 0 |
|
mohibur_rahman:
2020-07-02 14:35:37
Can anybody tell me why my code shows result 100 instead of accept? |
|
coolboy7:
2020-06-29 11:45:20
|
Added by: | Nikola P Borisov |
Date: | 2008-10-20 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |