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
Sukeesh:
2016-01-05 20:41:20
easy .. :) |
|
fallingstar:
2016-01-03 01:45:36
@sailemaverit partial score problems don't count |
|
sailemaverit:
2015-11-05 07:04:10
I have solved this problem, getting a 100 in the result.
|
|
Osama Fathy:
2015-10-17 21:30:02
I am confused!
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2015-08-09 14:26:11
@hoc sinh test: do the kid even care about spanning trees? :p |
|
hoc sinh test:
2015-07-23 15:41:32
Problem for kids :D Last edit: 2015-07-23 17:17:08 |
|
Ðức Tân:
2015-07-23 12:41:22
dễ vãi :D |
|
computer science:
2015-07-10 10:04:38
easy |
|
tarunsai:
2015-06-20 08:48:21
if we get 18.18 is it correct or not
|
|
bholagabbar:
2015-05-24 07:06:46
Edit: Do not pick the first element from a vector and resize it again and again. This will case TLE as removing an element from the start of a vector causes it to resize taking O(n) time. Instead sort it in descending order nad keep poping the elements from the back which take O(1) time. I managed to get 100 Last edit: 2015-05-26 09:26:07 |
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 |