#O1043. 最小生成树

最小生成树

题目描述

给定 nn 个点、mm 条带权边的无向图,求最小生成树的边权和。若图不连通输出 -1。

题目类型

最小生成树、Kruskal

输入格式

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

接下来 mm 行,每行三个整数 u,v,wu, v, w。

输出格式

一行一个整数,表示最小生成树边权和,不连通输出 -1。

样例 #1

样例输入 #1

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

样例输出 #1

7

数据规模与约定

数据范围 说明
1≤n≤2×1051 \le n \le 2 \times 10^5 点数
0≤m≤4×1050 \le m \le 4 \times 10^5 边数
1≤w≤1061 \le w \le 10^6 边权
  • 边权排序后并查集合并,答案用 long long。