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 --C3有三条路。如果全部修总代价25310太浪费。4其实修A-B B-C总代价5所有城市仍然连通。这就是最小生成树MST第三幕什么叫生成树1、有的同学会问为什么叫生成树1假设有4个城市。全部修A-----B |\ /| | \ / | | / \ | |/ \| C-----D里面有很多圈。2其实有些路可以拆掉。3最后A | B | C | D或者A / \ B C | D4只要所有点连通。没有环。这就是生成树。2、为什么要最小1因为生成树有很多种。2我们要总代价最小。3所以叫最小生成树Minimum Spanning Tree第四幕怎样才能花的钱最少这就是整道题最关键的问题。1假设现在有这些边长度 8 2 5 1 9 32如果你是国王。你会先修哪条3当然最便宜所以第一条原则先修最短的路。4于是排序变成1 2 3 5 8 9是不是就结束了不是第五幕为什么不能一直修1来看A / \ 2 3 / \ B --- 1 ---C2已经修了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 i1;in;i) for(int ji1;jn;j)枚举所有点对。2、第二步距离超过L。不能修。直接不要。if(dx*dxdy*dyl*l) continue;为什么不用sqrt(...)因为开方慢。比较平方即可。3、第三步剩下边。按照长度排序。例如1 2 3 5 8越来越长。4、第四步从小到大加入。如果不会形成环。修。否则跳过。直到修了n-1条边。结束。5、Kruskal流程图所有边 ↓ 排序 ↓ 最短边 ↓ 形成环 ↓ 否 ↓ 加入 ↓ 继续 ↓ 已经加入 n-1 条 ↓ 结束是不是很简单第七幕怎样判断有没有形成环1、这是八级最重要的数据结构并查集Union Find2、假设1开始A B C D四个人。互相不认识。2编号A B C D3现在修A-B于是A和B成为一家人。4再修B-C现在ABC是一家。5最后如果修A-C会怎样6并查集一查发现他们已经是一家。说明形成环。不能修。7这就是并查集最大的作用快速判断两个点是否已经连通。第八幕为什么最后要判断tn-11生成树有一个性质n个点一定只有n-1条边。例如5个点。一定4条边。2否则要么不连通。要么有环。3因此最后如果tn-1说明还有点没连上。输出Impossible这就是题目的要求。第九幕完整算法流程整道题其实就是下面这一张图。读入坐标 │ ▼ 枚举所有点对 │ ▼ 距离≤L │ 否│继续 ▼ 加入边集 │ ▼ 按照长度排序 │ ▼ 依次枚举边 │ ▼ 并查集判断 是否形成环 │ 是│跳过 ▼ 加入生成树 │ ▼ 统计总代价 │ ▼ 加入边n-1 │ 是│输出答案 否│Impossible第十幕为什么这题选择Kruskal而不是Prim1、有的同学都会问Prim也能求最小生成树呀答案是当然能。2、但是本题1先要判断距离≤L还要枚举所有点对。天然就生成了一张边表Edge List2而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; // 长度 }; // // 所有边 // vectorEdge 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) { xFind(x); yFind(y); parent[x]y; } // // 排序规则 // bool cmp(Edge a,Edge b) { return a.wb.w; } int main() { int n,L; cinnL; vectorpairint,int point(n1); // 输入坐标 for(int i1;in;i) { cinpoint[i].firstpoint[i].second; parent[i]i; // 初始化并查集 } // 建边 for(int i1;in;i) { for(int ji1;jn;j) { int dxpoint[i].first-point[j].first; int dypoint[i].second-point[j].second; if(dx*dxdy*dyL*L) continue; Edge e; e.ui; e.vj; e.wsqrt(dx*dxdy*dy); edge.push_back(e); } } // 排序 sort(edge.begin(),edge.end(),cmp); double ans0; int cnt0; // Kruskal for(auto e:edge) { if(Find(e.u)Find(e.v)) continue; Union(e.u,e.v); anse.w; cnt; // 已经形成生成树可以提前结束 if(cntn-1) break; } if(cntn-1) coutfixedsetprecision(2)ans; else coutImpossible; }第十二幕程序详细解析步骤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.365就是1 -------- 3 长度2.363、我们需要很多很多边1当然不能只存一条。于是vectorEdge edge;2就是建立边仓库以后算出来一条边。就放进去。3例如1——2 ↓ push_back() ↓ 仓库4再来一条2——5 ↓ push_back() ↓ 仓库以后所有边都在这里。4、怎样比较两条边1排序的时候。sort不知道什么叫短。2所以我们告诉它。bool cmp(Edge a,Edge b) { return a.wb.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 i1;in;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 ↓ 54以后再找1。程序一路找1 ↓ 2 ↓ 5找到5。5然后顺便把1 ↓ 5以后不用绕路了。这就叫路径压缩。7、 Union函数1官方写了一句f[getf(x)]getf(y);有的同学看起来有点累。2我们写成函数。void Union(int x,int y) { xFind(x); yFind(y); parent[x]y; }一下就清楚了。3第一步找到两个家长。4第二步让x家搬到y家结束。8、 建边1这里是整个程序最好理解的一部分。for枚举所有点。① ② ③ ④2两两之间计算距离。如果≤L说明可以修。加入edge3代码写成Edge e; e.ui; e.vj; e.wsqrt(...); 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() anse.w;10、 判断是否提前结束1提前结束条件已经修了 n-1 条边。2生成树永远n个点 ↓ n-1条边这是数学性质。3所以if(cntn-1)立即结束。还能快一点。第十三幕这道题考察了哪些知识知识点是否重点本题作用二维坐标距离⭐⭐⭐建立边不开平方比较平方⭐⭐⭐⭐判断是否超过L最小生成树Kruskal⭐⭐⭐⭐⭐核心算法并查集Union-Find⭐⭐⭐⭐⭐判断是否形成环排序sort⭐⭐⭐⭐按边权从小到大处理这是一道典型的图论综合题。它把几何建图 边集构造 排序 并查集 Kruskal 最小生成树完整串联了起来是八级具有代表性的编程题之一。最后送给同学们一句 Kruskal 的口诀先建边再排序边最短优先取并查集判成环不是一家就合并修满n-1条边最小生成树就完成只要记住这五句话今后遇到绝大多数Kruskal 最小生成树的题目都能迅速建立正确的解题思路。