给定一个无向连通图,求出它的最小生成树。
由于最小生成树可能有多种,因此答案只需要给出最后得到的最小生成树的边总权值。
若有n个点,则各个点以整数0到n-1编号。
给定一个无向连通图,求出它的最小生成树。
由于最小生成树可能有多种,因此答案只需要给出最后得到的最小生成树的边总权值。
若有n个点,则各个点以整数0到n-1编号。
第一行为一个数字,表示总点数。
之后的每一行,格式为3个数字,以空格隔开,分别为相连的两个点的编号,它们的边的权值。
注:输入为无向图。如果出现了“0 1 50”表示点0和点1之间有一条边,权值为50,则不会再出现“1 0 50”输入。
样例输入6
0 1 6
0 2 1
0 3 5
1 2 5
1 4 3
2 3 7
2 4 5
2 5 4
3 5 2
4 5 6
| 样例输出15 |
学习两种最小生成树的算法。
图偏稀疏,注意内存限制,建议使用vector实现邻接表来存储图。