信奥赛C++提高组csp-s之最小生成树算法Kruskal（案例实践）-平芜编程栈

信奥赛C++提高组csp-s之最小生成树算法Kruskal（案例实践）

最短网络 Agri-Net

题目背景

Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过10 5 10^5105。

输入格式

第一行农场的个数N NN（3 ≤ N ≤ 100 3 \leq N \leq 1003≤N≤100）。

接下来是一个N × N N \times NN×N的矩阵，表示每个农场之间的距离。理论上，他们是N NN行，每行由N NN个用空格分隔的数组成，实际上，由于每行80 8080个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是0 00，因为不会有线路从第i ii个农场到它本身。

输出格式

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

输入输出样例 #1

输入 #1

4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0

输出 #1

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,t,k=0;// n:农场数量，t:临时变量，k:边的计数器// 定义边的结构体structnode{intx,y,w;// x和y表示边的两个端点，w表示边的权重（距离）}a[10000];// 存储所有边的数组// 比较函数，用于将边按权重从小到大排序boolcmp(node a,node b){returna.w<b.w;}intfa[110];// 并查集数组，用于记录每个节点的父节点// 并查集的查找函数，带路径压缩intfind(intx){if(fa[x]!=x)returnfa[x]=find(fa[x]);// 路径压缩returnfa[x];}// 并查集的合并函数voidunionSet(intx,inty){introotx=find(x);introoty=find(y);if(rootx==rooty)return;// 如果已经在同一集合，不进行合并fa[rooty]=rootx;// 合并两个集合}intmain(){cin>>n;// 读取农场数量// 读取距离矩阵并构建边集for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cin>>t;// 读取i到j的距离// 只处理上三角矩阵，避免重复添加边if(i<j){k++;// 边计数器增加a[k].x=i;// 记录起点a[k].y=j;// 记录终点a[k].w=t;// 记录权重}}}// 将所有边按权重从小到大排序sort(a+1,a+k+1,cmp);// 初始化并查集，每个节点的父节点初始化为自己for(inti=1;i<=n;i++){fa[i]=i;}intsum=0;// 最小生成树的总权重intcnt=0;// 已选边的计数器// 遍历所有边，构建最小生成树for(inti=1;i<=k;i++){// 如果当前边的两个端点不在同一连通分量中if(find(a[i].x)!=find(a[i].y)){unionSet(a[i].x,a[i].y);// 合并两个连通分量sum+=a[i].w;// 累加权重cnt++;// 已选边数增加// 当已选边数达到n-1时，最小生成树构建完成if(cnt==n-1){cout<<sum;// 输出结果return0;// 提前结束程序}}}return0;}

功能分析

1. 问题理解

这是一个典型的最小生成树问题，需要在给定的完全图中找到连接所有节点的最小权重子图。

2. 算法选择

使用 Kruskal 算法，其核心思想是：

将所有边按权重从小到大排序
依次选择权重最小的边，如果该边不会形成环，则加入最小生成树
使用并查集高效地检测环

3. 关键步骤

输入处理：

读取 n×n 的距离矩阵
将矩阵转换为边列表，只处理上三角部分避免重复

并查集操作：

find(): 查找根节点并进行路径压缩
unionSet(): 合并两个集合

最小生成树构建：

按权重排序所有边
依次处理每条边，使用并查集判断是否形成环
当选择 n-1 条边时完成构建

4. 复杂度分析

时间复杂度：O(E log E)，主要来自排序操作
空间复杂度：O(N²)，存储边集

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
三、csp高频考点知识详解及案例实践：
- CSP信奥赛C++之动态规划
- CSP信奥赛C++之标准模板库STL
- 信奥赛C++提高组csp-s知识详解及案例实践
四、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

信奥赛C++提高组csp-s之最小生成树算法Kruskal（案例实践）