#MYD7. 道路连接

道路连接

题目描述

给定一个 n 个点、m 条边的无向带权连通图(点编号 1…n,可能有重边,但无自环)。求该图最小生成树的边权总和。

输入格式

第一行两个整数 n 和 m。接下来 m 行,每行三个整数 u, v, w,表示一条连接 u 与 v、权为 w 的无向边。

输出格式

一行一个整数,表示最小生成树的边权总和。

数据范围

1 ≤ n ≤ 100000,1 ≤ m ≤ 200000,1 ≤ u, v ≤ n,u ≠ v,1 ≤ w ≤ 10^9。图保证连通。

样例

4 5
1 2 1
1 3 4
2 3 2
3 4 3
2 4 5
6

说明/提示

Kruskal 或 Prim 均可。

解析

思路:Kruskal——按边权升序排序,用并查集依次合并不连通的边,恰选 n−1 条。

复杂度:O(m log m)。

来源

人工命题 · 三方对比实验