算法与数据结构实验题 10.23 寡人的难题

题目内容

★实验任务

寡人心系天下为国为民，想要在历史中留下点痕迹，就必须要让国家强盛起来，正所谓想致富先修路，寡人觉得去修路，那些吃干饭的大臣给了寡人很多条要修的道路，奈何国库空虚，寡人只能选择其中一些道路，把重点城市连接在一起，并且这些道路的花费要最少，寡人决定让你来接受这个任务，替寡人分忧。

★数据输入

第一行有两个正整数n，m，表示有n个城市（城市按照1到n编号），m条道路可选择，

接下来有m行，每行有三个正整数u，v，c，分别表示这一条道路连通u和v且花费黄金c两。

（1<=n<=50000,n-1<=m<=200000,1<=c<=10000）

★数据输出

输出能连通所有城市的道路的最小花费。

输入示例

3 3
1 2 3
2 3 4
1 3 2

输出示例

5

题目分析

把重点的城市链接在一起 -> 连接图上所有的点

道路的花费最小 -> 总权和最小

题目看到这里, 题意其实很明显了. 没有什么别的东西, 就是要求给定的图的最小生成树.

选择算法

目前学习到的只有两种算法: Prim 和 Kruskal. 选择哪种呢? 来看看区别

• Prim 算法

这个算法的基本思想是从小到大加入点.

任意选择一个起点, 按照贪心的原则, 不断的往图中添加距离最小的一个点, 直到图中有 n 个点.

不细说, 实现比 Kruskal 复杂. 这题我偷懒了, 主要谈谈本题用到的 Kruskal 算法.