传统题 1000ms 256MiB

最小生成树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定结点数为 nn,边数为 mm 的带权无向连通图 GG,所有结点编号为 1,2,,n1,2,\cdots,n

GG 的最小生成树的边权和。

输入格式

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

之后的 mm 行,每行三个正整数 ui,vi,wiu_i,v_i,w_i1ui,vin1\le u_i,v_i\le n0wi1090\le w_i\le 10^9),描述一条连接结点 uiu_iviv_i,边权为 wiw_i 的边。

输出格式

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

样例

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
16

数据范围与提示

1n2×1051\le n\le 2\times 10^50m5×1050\le m\le 5\times 10^5

「图论专题3」最小生成树

未参加
状态
已结束
规则
IOI
题目
10
开始于
2022-4-27 10:45
结束于
2022-5-27 10:45
持续时间
720 小时
主持人
参赛人数
8