#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)。
来源
人工命题 · 三方对比实验