2026年6月GESP真题及题解C八级线网建设题目描述A 市有n nn座基站需要通过线网互相连接。第i ii座基站位于二维平面上坐标( x i , y i ) (x_i, y_i)(xi​,yi​)处。第i ii座基站与第j jj座基站之间的距离定义为( x i − x j ) 2 ( y i − y j ) 2 \sqrt{(x_i - x_j)^2 (y_i - y_j)^2}(xi​−xj​)2(yi​−yj​)2​。如果两座基站之间的距离不超过给定的整数l ll那么可以修建连接这两座基站的线路线路长度为基站间的距离。如果从一座基站出发经过一系列线网中的线路可以到达另一座基站则称这两座基站是互相连接的。请问使得n nn座基站两两之间都互相连接需要修建的线路总长度最小是多少如果不能修建满足条件的线网则输出Impossible。输入格式第一行两个正整数n , l n, ln,l分别表示基站数量与线路长度上限。接下来n nn行每行两个整数x i , y i x_i, y_ixi​,yi​表示基站的坐标。输出格式输出一行。如果能修建满足条件的线网则输出需要修建的最小线路总长度保留两位小数。否则输出Impossible。输入输出样例 1输入 14 2 1 0 -1 -1 0 0 1 1输出 13.41输入输出样例 2输入 24 1 1 0 -1 -1 0 0 1 1输出 2Impossible数据范围对于40 % 40\%40%的测试点保证1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100。对于所有测试点保证1 ≤ n ≤ 500 1 \le n \le 5001≤n≤5001 ≤ l ≤ 100 1 \le l \le 1001≤l≤100− 100 ≤ x i , y i ≤ 100 -100 \le x_i, y_i \le 100−100≤xi​,yi​≤100。思路分析本题的本质是**最小生成树MST**问题。将基站视为图中的顶点。若两点间的欧氏距离 ≤ l则存在一条可修建的边边权即为实际距离。目标是使图连通且总边权最小——这正是 MST 的定义。若所有可建边构成的图本身不连通则无解输出Impossible。算法步骤读入 n, l 及 n 个点坐标。枚举所有点对 (i, j)计算距离平方d2。若d2 ≤ l²则将该边加入边集边权为sqrt(d2)。将边集按边权升序排序使用自定义比较函数cmp。用并查集执行 Kruskal依次取边若两端点不属于同一集合则合并累加总长度记录合并次数。若合并次数达到 n-1则输出总长度保留两位小数否则输出Impossible。复杂度边数 O(n²) ≤ 125k排序 O(m log m)并查集接近 O(m α(n))完全可行。代码实现#includebits/stdc.husingnamespacestd;structP{intx,y;};//点坐标structE{intu,v;doublew;};//边intn,l,f[505];//并查集父数组P p[505];//点集vectorEe;//边集intfd(intx){returnf[x]x?x:f[x]fd(f[x]);}//查找boolcmp(constEa,constEb){returna.wb.w;}//比较边权intmain(){scanf(%d%d,n,l);for(inti1;in;i)scanf(%d%d,p[i].x,p[i].y);longlongL1LL*l*l;for(inti1;in;i)for(intji1;jn;j){longlongdxp[i].x-p[j].x,dyp[i].y-p[j].y;longlongd2dx*dxdy*dy;if(d2L){doublewsqrt((double)d2);e.push_back({i,j,w});}}sort(e.begin(),e.end(),cmp);//按边权升序for(inti1;in;i)f[i]i;//初始化并查集doubleans0.0;intcnt0;for(autoed:e){intfufd(ed.u),fvfd(ed.v);if(fu!fv){f[fu]fv;ansed.w;if(cntn-1)break;}}if(cntn-1)printf(%.2f\n,ans);elseprintf(Impossible\n);return0;}功能分析输入读取 n、l 和所有点的坐标。建图双重循环枚举所有点对利用整数平方比较避免浮点误差仅当距离不超过 l 时创建边并精确计算欧氏距离作为边权。最小生成树采用 Kruskal 算法借助并查集动态维护连通分量。边按权值从小到大处理若连接两个不同分量则合并累加总长度。连通判断成功合并 n-1 条边表示图连通输出总长度保留两位小数否则输出Impossible。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.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 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}