给一个 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 算法。