3717 - 无向图最小生成树
描述

给一个 N 个点 M 条边的无向图(可能包含重边),求它的最小生成树的边权之和。若图不连通、无法构成生成树,则输出 No Solution。

输入

第1行:两个整数 N 和 M,中间用空格分隔。N 为点数,M 为边数(2 <= N <= 1000,1 <= M <= 100000)。
第2 ~ M+1 行:每行三个整数 u、v、w,表示一条连接 u 与 v、权值为 w 的边(1 <= u,v <= N,1 <= w <= 109)。

输出

如果存在最小生成树,输出一个整数表示其边权之和;否则输出 No Solution。

样例

输入

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

输出

7
提示

使用 Kruskal 算法:将边按权值从小到大排序,用并查集依次选取不会构成环的边,直到选出 N-1 条边。若最终选出的边数少于 N-1,说明图不连通,无解。也可使用 Prim 算法。

来源
51nod
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1