【算法速成课1

发布时间：2025-09-01 09:33

编程算法课程提升逻辑思维 #生活技巧# #自我提升技巧# #技能提升课程#

hansang_IR2025-08-29 0:29

碎碎念：

其实这个难度的算法才适合加到《再来一遍一定记住的算法（那些你可能忘记了的算法）》专栏。

但现在这个专栏都默认是数论团建了，之后会出一个"算法速成课"专栏，

对标"再来"专栏的长篇大论，较简单的算法保证半小时以内就能看懂。

前导：

给你一堆无向边，它们互相连通。

我们想从中选出几条边，它们边权加起来最小，且互相连通。

应该怎么做？

这是求最小生成树算法，听上去很有用对吧？

最小生成树（Minimum Spanning Tree, MST）：

是指在一个连通无向图 中，能够连接所有顶点 且边的权重总和最小的树结构。

这在生活中也很有用，比如：导航路线规划、电网选择。

解析：

求出最小生成树 的算法有两种，Prim 和 Kruskal。

Prim 适合稠密图（边数接近顶点数平方的图），

Kruskal 则适合稀疏图（边数远小于顶点数平方的图）。

一般我们用 Kruskal，总体较快常数小，但两个都要学（着重背 Kruskal）。

Prim：

Prim 算法是一种贪心算法，从一个起始顶点开始，逐步扩展生成树：

从任意顶点开始，将其加入生成树集合。重复选择与当前生成树相连的最小权重边。将新顶点加入生成树，直到覆盖所有顶点。注释代码：

cpp 复制代码

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5e5 + 10; struct node{int x; LL v; } ; vector<node> G[N]; bool v[N]; //v[i]：为 ture就是 i走过，反之则没有 int n, m; bool operator<(node na, node nb) {return na.v > nb.v; } void Prim(){LL ans = 0;priority_queue<node> Q;memset(v, 0, sizeof(v));int st = 1, sum = 1; // st：起始点，sum：走过多少点v[st] = 1;for(auto i: G[st]) {Q.push(i);}int Time = 0; //特判是否是连通图用的循环次数计数while (sum < n) {if (Time > 3 * m) { //每条边最多走两遍，超过三遍那肯定不连通cout << "orz" << "\n";return ;}Time++; //不能放下面那个 if(v)下面！！！auto Head = Q.top();Q.pop();int x = Head.x;if (v[x]) { //虽然下面进堆之前就特判了//但是历史遗留的边的点可能已经走过了continue;}v[x] = 1;sum++;ans += Head.v;for (auto j: G[x]) if(!v[j.x]) {Q.push(j);}}cout << ans << "\n"; } int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y; LL v;cin >> x >> y >> v;G[x].push_back({y, v});G[y].push_back({x, v});}Prim();return 0; } 关于时间复杂度：

以下 N 是点数，M 是边数。

我用的是二叉堆 + while，时间复杂度是。

（实际 while 次数会比 N 多，大概在 M 左右，常数为 2）

在洛谷上平均跑 300ms 以下，常数还行。

Kruskal：

Kruskal 算法也是一种贪心算法，但它是基于边的选择：

将所有边按权重从小到大排序。依次选择最小权重的边。如果该边连接的两个顶点不在同一连通分量中（不形成环），则加入生成树。重复步骤 2 和 3，直到选够 N - 1 条边（N 是节点个数）。注释代码：

cpp 复制代码

#include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; typedef long long LL; int fa[N]; struct node {int x, y;LL v; } a[N]; bool cmp(node na, node nb) {return na.v < nb.v; } int findfa(int x) {if (fa[x] == x) {return fa[x];}return fa[x] = findfa(fa[x]); } int main() {ios::sync_with_stdio(false);cin.tie(0);int n, m;cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> a[i].x >> a[i].y >> a[i].v;}for (int i = 1; i <= n; i++) {fa[i] = i;}LL ans = 0; //累计答案int sum = 0; //累计已选的边数sort(a + 1, a + m + 1, cmp);for (int i = 1; i <= m; i++) {int tx = findfa(a[i].x);int ty = findfa(a[i].y);if (tx != ty) {sum ++;ans += a[i].v;fa[tx] = ty;}if (sum == n - 1) { //找够边就退出break;}}if (sum < n - 1) { //都结束了还选不到 n - 1 条合适的边，包不连通的cout << "orz" << "\n";return 0;}cout << ans << "\n";return 0; } 关于时间复杂度：

以下 N 是点数，M 是边数。

我用的是排序 + 并查集，总时间复杂度大概是。

压缩路径并查集的时间极快，基本可以算常数。

外面套个 for 就是。

在洛谷上平均跑 200ms 以下。