题目描述
最小生成树(Minimum Spanning Tree,简称MST)是指在一个加权的、无向的连通图中,由所有顶点构成的一个子图,这个子图是一棵树,并且其所有边的权重之和最小。换句话说,最小生成树是在保证图中所有顶点连通的前提下,使得连接这些顶点的边的总成本最低的一棵树。
现给出一个无向图,需要你求出最小生成树,如果该图不连通,则输出 orz。
输入
第一行包含两个整数 n,m,表示该图共有 n 个结点和 m 条无向边。 接下来m行,每行三个整数x、y、z,表示有一条路径可以从x到y,长度为z。输出
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。 如果该图不连通则输出 orz。数据范围
1≤n≤100,1≤m≤1000,1≤z≤1000 特殊情况:可能有两条路可以从x直达y输入样例
4 51 2 2
1 3 2
1 4 3
2 3 4
3 4 3