同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1598_最小生成树

2022-5-16 18:17| 发布者: Hocassian| 查看: 45| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950414743500-Problem List-采集的数据-后羿采集器.html

Pro.ID

1598

Title

最小生成树

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1598

AC

Submit

Ratio

35.29%

时间&空间限制

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

给定节点数为 n，边数为 m 的带权无向连通图 G，所有节点编号为 1, 2, ⋯, n。

求 G 的最小生成树的边权和。

输入

第一行两个正整数 n , m。

之后的 m 行，每行三个正整数 u_i, v_i, w_i （1 ≤ u_i, v_i ≤ n，0 ≤ w_i ≤ 10⁹ ），描述一条连接节点 u_i 和 v_i ，边权为 w_i 的边。

1 ≤ n ≤ 2×10⁵ ，0 ≤ m ≤ 5×10⁵ 。

输出

Description

给定节点数为 n，边数为 m 的带权无向连通图 G，所有节点编号为 1, 2, ⋯, n。

求 G 的最小生成树的边权和。

Input

第一行两个正整数 n , m。

之后的 m 行，每行三个正整数 u_i, v_i, w_i （1 ≤ u_i, v_i ≤ n，0 ≤ w_i ≤ 10⁹ ），描述一条连接节点 u_i 和 v_i ，边权为 w_i 的边。

1 ≤ n ≤ 2×10⁵ ，0 ≤ m ≤ 5×10⁵ 。

Output

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

Sample Input

7 12
1 2 9
1 5 2
1 6 3
2 3 5
2 6 7
3 4 6
3 7 3
4 5 6
4 7 2
5 6 3
5 7 6
6 7 1

Sample Output

Author

John

样例输入