问题 A: 最小生成树

问题 A: 最小生成树

时间限制: 1 Sec  内存限制: 16 MB
提交: 1173  解决: 182
提交 状态 算法问答 

题目描述

给定一个无向连通图,求出它的最小生成树。

由于最小生成树可能有多种,因此答案只需要给出最后得到的最小生成树的边总权值。

若有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实现邻接表来存储图。

提交 状态