[数据结构与算法]工作准备-00

工作准备–复习

马上需要找工作了，需要进行复习。所以从现在开始逐渐复习，现将每天所得记录下来，以便后来复习以及其他人也可以作为参考。
在牛客上刷题，遇到一道编程题，编程题如下：
题目：
地铁迷在某个城市组织了地铁打卡活动。活动要求前往该城市中的所有地铁站进行打卡。打卡可以在站外或者站内进行。地铁的计价规则如下：只要不出站，就不计费；出站时，只计算进站和出站站点的距离。如在同一个站点进出站，按照最低票价 a 元计算。假设地铁票不会超时。大部分站点都是通过地铁线连通的，而且地铁站的连通是双向的（若 A，B 连通，则 B，A连通），且具有传递性的（若 A，B 连通，且 B，C 连通，则 A，C连通）。但并不是所有的地铁站都相互连通，在不能通过坐地铁达到的两个地点间，交通的花费则提高到 b 元。地铁迷从酒店起点出发，再回到酒店。假设从酒店到达任意地铁站的交通花费为 b 元。请计算地铁迷完成打卡最小交通花费。
案例：
输入如下：n m a b
第一行：8 7 3 6 分别代表：站点数n 站点连接对数m 最低票价a 交通花费b
其中站点对有以下组合：
0—>1
1—>2
2—>3
0—>3
4—>5
5—>6
6—>7

参考代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 50;
int n, m, a, b, u, v;
int parent[N];
//寻找根节点的函数，并作路径压缩
/*如果节点x和他的父节点相同，则x就是根节点，直接返回；
否则，继续寻找x父节点的父节点，直到找到
根节点后返回，并将节点x的父节点改为根节点。*/
int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}
//合并两个节点，把其中一个节点的父亲换成另一个节点
void to_union(int i, int j) {
	parent[find(i)] = find(j);
}
int main()
{
	cin >> n >> m >> a >> b;
        //初始化：所有节点的父节点都是自己，即自身就是根节点
	for (int i = 0; i<n; i++) {
		parent[i] = i;
	}
        //合并两个节点
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		to_union(u, v);
	}
	int cnt = 0;
        //寻找根节点个数
	for (int i = 0; i<n; i++) {
		if (parent[i] == i) {
			cnt++;
		}
	}
        //计算票价
	int ans = b + b + (cnt - 1)*b + cnt*a;
	printf("%d\n", ans);
	return 0;
}

代码思路分析：
首先需要从输入到的数据中获取到需要进行计算的链表：开始是以每个站点为头节点，之后根据站点之间的连接关系生成对应的链表，其中生成链表的主要算法就是find()函数和to_union()函数，这两个函数就是设置parent[头节点值] = 下一节点值。
后面的cnt是用来统计站点组成的链表中孤立链表的个数。
ans是最少花费走完这所有站点。b+b表示从宾馆到第一个站点，再从最后一个站点到宾馆的费用，这个费用是固定不变的。从一个孤立站点到另一个孤立站点需要花费b，所以总共需要(cnt - 1)b；一个孤立站点所组成的链表所要花费的最少钱数等于a，所以总共需要花费cnta；
最后计算出来的结果ans即为走遍这些个站点所需花费最少的费用。