牛客4633题，寻宝：最小生成树算法实战解析
https://dajuwangluo.cn/zb_users/upload/2025/06/202506211750438683184847.jpg一、问题理解与算法选择这道题目描述了一个典型的图论问题：在保证所有节点连通的前提下，选择边的集合使得总成本最小，同时关注所选边中的最大值。这正是**最小生成树(MST)**问题的变形，我们可以使用Kruskal或Prim算法解决。由于题目需要找出最长的那根木材，Kruskal算法更为合适，因为它能按边权排序，方便记录最大边。二、完整C++代码实现#include <iostream>#include <vector>
#include <algorithm>
using namespACe std;
// 并查集数据结构用于检测环路
struct UnionFind {
vector<int> parent;
UnionFind(int n) : parent(n+1) {
for(int i = 1; i <= n; ++i)
parent = i;
}
int find(int x) {
if(parent != x)
parent = find(parent);
return parent;
}
bool unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY) return false;
parent = rootX;
return true;
}
};
struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
int main() {
int N, M;
cin >> N >> M;
vector<Edge> edges(M);
for(int i = 0; i < M; ++i) {
cin >> edges.u >> edges.v >> edges.weight;
}
// Kruskal算法核心步骤
sort(edges.begin(), edges.end());
UnionFind uf(N);
int maxWood = 0, edgeCount = 0;
for(const auto& e : edges) {
if(uf.unite(e.u, e.v)) {
maxWood = max(maxWood, e.weight);
if(++edgeCount == N - 1) break;
}
}
cout << (edgeCount == N - 1 ? maxWood : -1) << endl;
return 0;
}
三、算法详解与优化
[*]并查集(Union-Find)数据结构：
[*]用于高效检测图中是否形成环路
[*]路径压缩优化使查找操作接近O(1)时间复杂度
[*]按秩合并可进一步优化（本实现未使用）
[*]Kruskal算法流程：
[*]将所有边按权值升序排序（O(M log M)）
[*]依次尝试加入每条边，使用并查集检测是否形成环路
[*]当选中N-1条边时即完成最小生成树构建
[*]时间复杂度分析：
[*]排序阶段：O(M log M)
[*]并查集操作：近似O(M α(N))，其中α是反阿克曼函数
[*]总体复杂度由排序决定，约为O(M log M)
[*]空间复杂度：
[*]存储边：O(M)
[*]并查集：O(N)
[*]总计：O(M + N)
四、新手学习指南
[*]理解图的基本概念：
[*]顶点（空地）、边（木材）、权重（木材长度）
[*]连通性要求（所有空地必须可达）
[*]最小生成树的核心思想：
[*]选择边的子集使图连通且总权重最小
[*]无环路且包含所有顶点（N-1条边）
[*]Kruskal算法的直观理解：
[*]"贪心"策略：每次选择当前最短的有效边
[*]避免环路：确保边的两个端点不在同一集合
[*]调试技巧：
[*]小规模测试用例验证
[*]检查边界条件（N=1，M=0等）
[*]输出中间结果辅助调试
五、常见问题解答Q: 为什么不能直接取所有边中最小的M-1条？ A: 这样可能无法保证图的连通性，必须确保选择的边能连接所有顶点。Q: 如何处理不连通图的情况？ A: 代码中通过edgeCount检查，如果最终不足N-1条边，输出-1（题目保证连通故未处理）。Q: 为什么使用并查集而不是DFS检测环路？ A: 并查集的时间复杂度更优，特别适合动态连通性检查。来源：牛客4633题，寻宝：最小生成树算法实战解析
页:
[1]