GESP2026年6月认证C++八级( 第三部分编程题（1、线网建设））精讲
第三部分 第一题
《线网建设》
——通信王国里的修路大师（Kruskal最小生成树）
第一幕：通信王国
1、很久很久以前。
程序大陆上，有一个十分发达的国家——
通信王国。
王国里有很多座通信基站。
每座基站都有自己的坐标，例如：
① (1,0) ② (3,2) ③ (5,1) ④ (2,4)2、国王希望：
任意两座基站，都能够互相通信。
但是……
修建线路可是要花钱的！
线路越长，花的钱越多。
更麻烦的是：
超过 L 米的线路根本修不了。
于是国王说：
"请你帮我设计一套最省钱的建设方案。"
这就是今天这道题。
第二幕：读懂题目
1、输入：
n个点。
2、每个点：
(x,y)坐标。
3、两个点之间距离
就是：
√((x1-x2)²+(y1-y2)²)但是：
只有
距离≤L才能修。
4、最后要求：
所有点连通。
总代价最小。
5、如果不能连通：
输出
Impossible6、举一个最简单的例子
（1）例如：
A B C三座城市。
（2）距离：
A-B 2 A-C 5 B-C 3画出来：
A 2 / \5 / \ B -- 3 --C（3）有三条路。
如果全部修：
总代价：
2+5+3=10太浪费。
（4）其实修：
A-B B-C总代价：
5所有城市仍然连通。
这就是：
最小生成树（MST）
第三幕：什么叫生成树？
1、有的同学会问：
为什么叫生成树？
（1）假设有：
4个城市。
全部修：
A-----B |\ /| | \ / | | / \ | |/ \| C-----D里面有很多圈。
（2）其实：
有些路可以拆掉。
（3）最后：
A | B | C | D或者：
A / \ B C | D（4）只要：
所有点连通。
没有环。
这就是：
生成树。
2、为什么要最小？
（1）因为：
生成树有很多种。
（2）我们要：
总代价
最小。
（3）所以：
叫
最小生成树（Minimum Spanning Tree）
第四幕：怎样才能花的钱最少？
这就是整道题最关键的问题。
（1）假设现在有这些边：
长度 8 2 5 1 9 3（2）如果你是国王。
你会先修哪条？
（3）当然：
最便宜！
所以：
第一条原则：
先修最短的路。
（4）于是排序：
变成：
1 2 3 5 8 9是不是就结束了？
不是！
第五幕：为什么不能一直修？
（1）来看：
A / \ 2 3 / \ B --- 1 ---C（2）已经修了：
A-B B-C现在：
A和C
其实已经能到达。
（3）如果：
再修
A-C会怎样？
（4）就出现：
环。
A / \ B---C这条边：
完全浪费。
（5）所以：
第二条原则：
形成环的边不能修。
（6）于是：
Kruskal算法
终于出现了。
第六幕：Kruskal算法
整个算法只有四句话。
1、第一步
把所有边算出来。
例如：
5个点。
两两之间：
1-2 1-3 1-4 ... 4-5全部记录。
本题就是：
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)枚举所有点对。
2、第二步
距离超过L。
不能修。
直接不要。
if(dx*dx+dy*dy>l*l) continue;为什么不用：
sqrt(...)因为：
开方慢。
比较平方即可。
3、第三步
剩下边。
按照长度排序。
例如：
1 2 3 5 8越来越长。
4、第四步
从小到大加入。
如果：
不会形成环。
修。
否则：
跳过。
直到：
修了：
n-1条边。
结束。
5、Kruskal流程图
所有边 ↓ 排序 ↓ 最短边 ↓ 形成环？ ↓ 否 ↓ 加入 ↓ 继续 ↓ 已经加入 n-1 条？ ↓ 结束是不是很简单？
第七幕：怎样判断有没有形成环？
1、这是八级最重要的数据结构：
并查集（Union Find）
2、假设：
（1）开始：
A B C D四个人。
互相不认识。
（2）编号：
A B C D（3）现在修：
A-B于是：
A和B
成为一家人。
（4）再修：
B-C现在：
ABC是一家。
（5）最后：
如果：
修：
A-C会怎样？
（6）并查集一查：
发现：
他们已经是一家。
说明：
形成环。
不能修。
（7）这就是：
并查集最大的作用：
快速判断两个点是否已经连通。
第八幕：为什么最后要判断
t==n-1（1）生成树有一个性质：
n个点，一定只有n-1条边。
例如：
5个点。
一定：
4条边。
（2）否则：
要么：
不连通。
要么：
有环。
（3）因此：
最后：
如果：
t<n-1说明：
还有点没连上。
输出：
Impossible这就是题目的要求。
第九幕：完整算法流程
整道题其实就是下面这一张图。
读入坐标 │ ▼ 枚举所有点对 │ ▼ 距离≤L？ │ 否│继续 ▼ 加入边集 │ ▼ 按照长度排序 │ ▼ 依次枚举边 │ ▼ 并查集判断 是否形成环？ │ 是│跳过 ▼ 加入生成树 │ ▼ 统计总代价 │ ▼ 加入边==n-1？ │ 是│输出答案 否│Impossible第十幕：为什么这题选择Kruskal，而不是Prim？
1、有的同学都会问：
Prim也能求最小生成树呀？
答案是：
当然能。
2、但是本题：
（1）先要判断：
距离≤L还要：
枚举所有点对。
天然就生成了一张：
边表（Edge List）
（2）而Kruskal最喜欢：
边表。
所以：
写起来，最自然。
第十一幕：参考程序：
1、官方参考程序：
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; // 最多500个点 const int N = 510; // 最多边数 // 两两连边，最多约 N*N 条 const int E = N * N; // n：基站数量 // l：允许修建线路的最大长度 int n, l; // 每个基站的坐标 int x[N], y[N]; // p：保存边的编号 // u：边的起点 // v：边的终点 int p[E], u[E], v[E]; // 当前共有多少条边 int cnt; // 并查集数组 // f[i]表示i的父节点 // 开始全部为0，表示自己就是集合代表 int f[N]; // t表示已经加入最小生成树的边数 int t = 0; // d保存每条边的长度 double d[E]; // 最终答案（最小生成树总长度） double ans = 0; ////////////////////////////////////////////////////// // 并查集——寻找祖先（带路径压缩） ////////////////////////////////////////////////////// int getf(int u) { // 如果没有父亲 // 自己就是祖先 if (f[u] == 0) return u; // 路径压缩 return f[u] = getf(f[u]); } ////////////////////////////////////////////////////// // 排序函数 // 按照边长从小到大排序 ////////////////////////////////////////////////////// bool cmp(int a, int b) { return d[a] < d[b]; } int main() { ////////////////////////////////////////////////// // 输入 ////////////////////////////////////////////////// cin >> n >> l; // 输入每个点坐标 for (int i = 1; i <= n; i++) cin >> x[i] >> y[i]; ////////////////////////////////////////////////// // 枚举所有边 ////////////////////////////////////////////////// for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { // 两点横坐标差 int dx = x[i] - x[j]; // 两点纵坐标差 int dy = y[i] - y[j]; // 如果距离超过L // 这条边不能修 // // 注意： // 比较平方即可 // 不需要sqrt() if (dx * dx + dy * dy > l * l) continue; // 新增一条边 cnt++; // 第cnt条边 p[cnt] = cnt; // 起点 u[cnt] = i; // 终点 v[cnt] = j; // 保存真正距离 d[cnt] = sqrt(dx * dx + dy * dy); } } ////////////////////////////////////////////////// // 所有边按长度排序 ////////////////////////////////////////////////// sort(p + 1, p + cnt + 1, cmp); ////////////////////////////////////////////////// // Kruskal ////////////////////////////////////////////////// for (int i = 1; i <= cnt; i++) { // 当前边编号 int id = p[i]; // 当前边两个端点 int pu = u[id]; int pv = v[id]; ////////////////////////////////////////////////// // 判断是否已经连通 ////////////////////////////////////////////////// if (getf(pu) == getf(pv)) continue; ////////////////////////////////////////////////// // 加入最小生成树 ////////////////////////////////////////////////// // 边数+1 t++; // 累加长度 ans += d[id]; ////////////////////////////////////////////////// // 合并两个集合 ////////////////////////////////////////////////// f[getf(pu)] = getf(pv); } ////////////////////////////////////////////////// // 判断是否成功生成树 ////////////////////////////////////////////////// // n个点 // 最小生成树必须有n-1条边 if (t == n - 1) printf("%.2lf\n", ans); else printf("Impossible\n"); return 0; }2、教学版
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <iomanip> using namespace std; const int MAXN = 505; //======================= // 一条边 //======================= struct Edge { int u; // 起点 int v; // 终点 double w; // 长度 }; //======================= // 所有边 //======================= vector<Edge> edge; //======================= // 并查集 //======================= int parent[MAXN]; //======================= // 查找祖先（路径压缩） //======================= int Find(int x) { if(parent[x]==x) return x; return parent[x]=Find(parent[x]); } //======================= // 合并两个集合 //======================= void Union(int x,int y) { x=Find(x); y=Find(y); parent[x]=y; } //======================= // 排序规则 //======================= bool cmp(Edge a,Edge b) { return a.w<b.w; } int main() { int n,L; cin>>n>>L; vector<pair<int,int>> point(n+1); // 输入坐标 for(int i=1;i<=n;i++) { cin>>point[i].first>>point[i].second; parent[i]=i; // 初始化并查集 } // 建边 for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int dx=point[i].first-point[j].first; int dy=point[i].second-point[j].second; if(dx*dx+dy*dy>L*L) continue; Edge e; e.u=i; e.v=j; e.w=sqrt(dx*dx+dy*dy); edge.push_back(e); } } // 排序 sort(edge.begin(),edge.end(),cmp); double ans=0; int cnt=0; // Kruskal for(auto e:edge) { if(Find(e.u)==Find(e.v)) continue; Union(e.u,e.v); ans+=e.w; cnt++; // 已经形成生成树，可以提前结束 if(cnt==n-1) break; } if(cnt==n-1) cout<<fixed<<setprecision(2)<<ans; else cout<<"Impossible"; }第十二幕：程序详细解析步骤
1、我们先不要写程序
而是先画流程图。
这道题应该先画：
输入坐标 │ ▼ 枚举所有点之间距离 │ ▼ 超过L？ 是─────────┐ │ │ │跳过 │保留 ▼ ▼ 加入边集 │ ▼ 所有边排序 │ ▼ Kruskal算法 │ ▼ 输出答案2、 第一件事情——设计一条边
（1）官方程序用了四个数组：
u[] v[] d[] p[]对于初学者不太好理解。
（2）我们可以把它们合成一个结构体。
struct Edge { int u; // 起点编号 int v; // 终点编号 double w; // 边长 };是不是舒服多了？
（3）一条边就是：
Edge 里面放： 起点 终点 长度（4）例如：
Edge 1 3 2.36（5）就是：
1 -------- 3 长度2.363、我们需要很多很多边
（1）当然不能只存一条。
于是：
vector<Edge> edge;（2）就是建立：
边仓库以后：
算出来一条边。
就放进去。
（3）例如：
1——2 ↓ push_back() ↓ 仓库（4）再来一条：
2——5 ↓ push_back() ↓ 仓库以后：
所有边都在这里。
4、怎样比较两条边？
（1）排序的时候。
sort不知道：
什么叫
"短"。
（2）所以我们告诉它。
bool cmp(Edge a,Edge b) { return a.w<b.w; }（3）意思就是：
谁短。
谁排前面。
（4）例如：
4.3 2.1 8.5 1.6排序以后：
1.6 2.1 4.3 8.5这就是Kruskal第一步。
5、 并查集重新写
（1）官方程序使用：
f[]我们改个名字。
int parent[505];是不是一下就知道：
父亲什么意思。
（2）初始化：
1 2 3 4 5每个人：
父亲都是自己。
for(int i=1;i<=n;i++) parent[i]=i;（3）画出来：
1 ↓ 12 ↓ 2......
谁也不认识谁。
6、Find函数
（1）这里也是我们教学的重点。
int Find(int x) { if(parent[x]==x) return x; return parent[x]=Find(parent[x]); }（2）为什么这样写？
举个例子。
（3）原来：
1 ↓ 2 ↓ 5（4）以后：
再找：
1。
程序：
一路找：
1 ↓ 2 ↓ 5找到：
5。
（5）然后：
顺便把：
1 ↓ 5以后：
不用绕路了。
这就叫：
路径压缩。
7、 Union函数
（1）官方写了一句：
f[getf(x)]=getf(y);有的同学看起来有点累。
（2）我们写成函数。
void Union(int x,int y) { x=Find(x); y=Find(y); parent[x]=y; }一下就清楚了。
（3）第一步：
找到两个家长。
（4）第二步：
让：
x家搬到：
y家结束。
8、 建边
（1）这里是整个程序最好理解的一部分。
for枚举：
所有点。
① ② ③ ④（2）两两之间：
计算距离。
如果：
≤L说明：
可以修。
加入：
edge（3）代码写成：
Edge e; e.u=i; e.v=j; e.w=sqrt(...); edge.push_back(e);（4）是不是比：
u[] v[] d[]好理解？
9、 Kruskal真正开始
（1）排序：
sort(edge.begin(),edge.end(),cmp);（2）这一句。
就是：
最短 ↓ 最长（3）然后：
开始修路。
for(auto e:edge)意思：
一条一条拿出来。
（4）例如：
第一条：
1——3第二条：
2——5......
（5）然后判断：
if(Find(e.u)==Find(e.v))什么意思？
就是：
看看：
是不是已经认识。
（6）进行判断：
认识：
跳过。
不认识：
修路。
Union() ans+=e.w;10、 判断是否提前结束
（1）提前结束条件：
已经修了 n-1 条边。（2）生成树永远：
n个点 ↓ n-1条边这是数学性质。
（3）所以：
if(cnt==n-1)立即结束。
还能快一点。
第十三幕：这道题考察了哪些知识？
| 知识点 | 是否重点 | 本题作用 |
|---|---|---|
| 二维坐标距离 | ⭐⭐⭐ | 建立边 |
| 不开平方比较平方 | ⭐⭐⭐⭐ | 判断是否超过L |
| 最小生成树（Kruskal） | ⭐⭐⭐⭐⭐ | 核心算法 |
| 并查集（Union-Find） | ⭐⭐⭐⭐⭐ | 判断是否形成环 |
| 排序（sort） | ⭐⭐⭐⭐ | 按边权从小到大处理 |
这是一道典型的图论综合题。它把几何建图 + 边集构造 + 排序 + 并查集 + Kruskal 最小生成树完整串联了起来，是八级具有代表性的编程题之一。
最后，送给同学们一句 Kruskal 的口诀
先建边，再排序；
边最短，优先取；
并查集，判成环；
不是一家就合并；
修满n-1条边，最小生成树就完成！
只要记住这五句话，今后遇到绝大多数Kruskal 最小生成树的题目，都能迅速建立正确的解题思路。