请编写程序,实现在带权的无向图中求最小生成树的 Prim 算法。
注意:当多个待收录顶点到当前点集的距离等长时,按编号升序进行收录。
输入格式:
输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。
随后 m 行,每行给出一条无向边两端点的编号、权重。顶点编号从 0 开始,权重(≤100)为整数。同行数字均以一个空格分隔。
输出格式:
参考样例。
首先在一行中输出 total weight = x
,其中 x
为最小生成树中所有边的总权重。如果最小生成树不存在,则 x
为 −1。
随后在一行中按顶点编号升序输出每个顶点在最小生成树中的父结点的编号。为输出简单起见,每个数字后有一个空格。
注意:此处默认顶点 0 为最小生成树的根结点,其父结点编号规定为 −1。算法初始化时,所有顶点(除了根结点)的父结点编号默认为 0。
输入样例 1:
6 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1
输出样例 1:
total weight = 11
-1 0 0 1 5 2
输入样例 2:
7 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1
输出样例 2:
total weight = -1
-1 0 0 1 5 2 0