算法与数据结构实验题 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 算法. ?

• Kruskal 算法

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

从权重最小的一条边开始, 按照贪心的原则, 不断的往图中添加权重最小的边。直到图中有 n - 1 条边.

本文使用的算法是 Kruskal 算法.

Kruskal 把所有的顶点以是否加入最小生成树为依据分为两个顶点集合.

生成算法从权重最小的边开始检查:

如果这条边不在最小生成树当中.

就将这条边加入到最小生成树当中. 这使得每次加入的边都是最优的, 或者说每次加入的边都是未加入的边当中最小的一条边.

如果这条边在最小生成树当中.

则跳过该边, 继续检查次小的边.

直到最小生成树中已经有 n 个顶点, 就退出循环. 最小生成树构建完毕.

在如图所示的无向连通图中, 应用 Kruskal 算法求最小生成树可以有如下过程:

---

Kruskal 算法的实现方法

我们需要怎样的数据结构来实现所需的操作呢? 要实现这个算法, 我们首先要解决下面三个问题.

如何存放图? 怎么每次都找到权重最小的边? 怎样知道这条边是不是已经在当前的最小生成树当中?

• 如何存放图

因为求解最小生成树的过程中, 并不涉及对某一条特定边或特定点的查询或是直接修改. 所以直接使用顺序表存储图就ok了.

• 怎么找权重最小的边.

线性遍历, 排序, 最小堆... 都可解决这个问题. 同样的, 最小生成树中并不涉及到对边集动态的查询修改等操作. 又关注到题目给定的权重的数据范围很小.

我们选择简单且快速的方法: 计数排序即可.

配合顺序表存储. 可以快速优雅地实现算法的前期初始化工作.

• 怎么知道这条边是不是已经在当前最小生成树当中

再回顾下我们刚刚提到的算法流程以及示例演示. 与其说我们关注某个点是否已经加入到当前的最小生成树中, 我们也可以等效的说我们关注的是与这几条边相关的顶点是否已经加入到了最小生成树之中.

合并-检查-合并-检查. 熟悉吗? 我们有一个专门实现这个功能的数据结构. 并查集!

在 Kruskal 算法中. 我们不难有以下结论:

• 检查一条边是否在最小生成树中 == 这两个点是否在最小生成树的顶点集合中

• 加入一条边 == 将相关的两个点加入到顶点集合当中

这用并查集可以极其方便的实现.

代码实现

了解完完整思路之后, 来看看代码要怎么写吧.

根据上述的思路. 我们先列出简单的伪代码.

	int main(void)
	{
		int 总权值 = 0;
		存储图;
		for (e : 权重最小的边)
		{
			尝试合并 e 进 MST 中
			{
				成功: 总权值 += e 的权重;
				失败: 继续循环, 检查下一条边;
			}
		}
	}

再将上述的讨论兑现成具体的代码.

有一点问题要额外注意一下.

在写这份解题报告的时候, 题目的测试数据是存在问题的.

题目给出的数据不一定是一个连通图. 也就是说, 有的城市可能根本就走不到.

要补充一个循环退出条件才可以 AC 本题. 即若所有边已经遍历完成, 则退出循环

整合一下代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;
inline int read();

class DisjointSet
{
	vector<int> _parent;	// 存储最小生成树中各个顶点连接关系
	vector<int> _size;		// 顶点的子节点个数. 启发式合并 unite() 用到的参考数据 (优化效率, 非必要代码可以去掉).
public:
	// 初始化并查集. _parent 枚举初始化. 函数 iota() 的意思是从 _parent 的首元素到末尾元素 按从 0, 1, 2, ..., n 的顺序初始化.
	// _size 全部置 1
	DisjointSet(int s) : _parent(s), _size(s, 1) { iota(_parent.begin(), _parent.end(), 0); }

	// 递归查找目标节点. 顺便压缩下路径.
	int find(int x) { return _parent[x] == x ? x : _parent[x] = find(_parent[x]); }
	// 合并 x <-- y. 返回值为合并是否成功.
	bool unite(int x, int y)
	{
		x = find(x), y = find(y);
		if (x == y) return false;	// 已经在一个集合内, 合并失败.
		if (_size[x] < _size[y])
			swap(x, y);				// 启发式合并, 使得每次都是小的集合加入到大的集合中. (非必要代码, 可删除)

		// 合并
		_parent[y] = x;				// 修改根节点指向
		_size[x] += _size[y];		// 更新合并后的子节点数量
		return true;
	}
};

struct Edge {int from, to;};

#define WEIGHT_MAX 10010
int main(void)
{
#ifdef LOCAL_COMPILE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// 初始化.
	// 存储图 & 按权重排序边.
	int n = read(); int m = read();
	int u, v, w, max = 0;				// 临时存储变量及输入权重的最大值(作为 Kruskal 的退出条件).
	vector<Edge> edgeSet[WEIGHT_MAX];	// 用计数排序的思想, 将边的权重作为 edgeSet 的下标, 在输入的过程中完成自然排序.
	for (int i = 0; i < m; i++)
	{
		u = read(); v = read(); w = read();		// 读入边
		edgeSet[w].push_back({u - 1, v - 1});	// 存储边
	}

	// Kruskal 算法.
	// 本题是有一个坑点在的, 题目给出的数据不一定是一个连通图. 也就是说, 有的城市可能根本就走不到. 体现在代码中多加一个循环退出条件.
	int ans = 0;
	DisjointSet mst(n);		// 并查集记录已连接的顶点.
	for (int i = 0, cnt = 1; cnt < n; i++)	// 从权重为 0 的边开始遍历, 当已经加入 n - 1 或者已经遍历了所有的边了, 就退出循环.
		for (auto j : edgeSet[i])						// 遍历权重为 i 的所有边
			if (mst.unite(j.from, j.to))				// 尝试将边 j 加入 MST. 若成功则更新答案, 若否继续循环.
			{
				ans += i;
				cnt++;
			}
	cout << ans;

	return 0;
}
inline int read()
{
	int ret = 0, sign = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
			sign = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		ret = (ret << 1) + (ret << 3) + (ch ^ 48);
		ch = getchar();
	}
	return ret * sign;
}

参考资料 Reference

最小生成树 - OI Wiki (oi-wiki.org)

并查集应用 - OI Wiki (oi-wiki.org)