题解：洛谷 P17016 [GESP202606 八级] 线网建设

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P17016 [GESP202606 八级] 线网建设【题目描述】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。【输入样例】4 2 1 0 -1 -1 0 0 1 1【输出样例】3.41【核心思想】问题分析给定n nn个基站的二维坐标和一个距离上限l ll只有当两基站间欧几里得距离≤ l \leq l≤l时才能修建线路。要求使所有基站两两连通的最小线路总长度若无法连通则输出Impossible。这是一个**最小生成树MST**问题核心在于从所有可修建线路中选取总长度最小且能连接所有基站的边集。算法选择Kruskal 算法将所有有效边按长度排序用并查集维护连通性贪心选取不形成环的最短边欧几里得距离筛选先计算所有点对距离仅保留≤ l \leq l≤l的边作为候选边关键步骤读入数据读取n , l n, ln,l和基站坐标( x i , y i ) (x_i, y_i)(xi​,yi​)构建有效边集枚举所有基站对( i , j ) (i, j)(i,j)计算欧几里得距离d ( x i − x j ) 2 ( y i − y j ) 2 d \sqrt{(x_i-x_j)^2 (y_i-y_j)^2}d(xi​−xj​)2(yi​−yj​)2​若d ≤ l d \leq ld≤l则加入边集Kruskal 算法将所有有效边按长度升序排序初始化并查集每个基站自成一个连通块遍历排序后的边若两端点不在同一连通块则合并并累加边长若最终选取边数 n − 1 n-1n−1则图不连通输出结果若连通输出总长度保留两位小数否则输出Impossible时间/空间复杂度时间复杂度O ( n 2 log ⁡ n 2 ) O ( n 2 log ⁡ n ) O(n^2 \log n^2) O(n^2 \log n)O(n2logn2)O(n2logn)枚举O ( n 2 ) O(n^2)O(n2)条边排序O ( n 2 log ⁡ n ) O(n^2 \log n)O(n2logn)并查集操作近似O ( 1 ) O(1)O(1)空间复杂度O ( n 2 ) O(n^2)O(n2)存储所有有效边最小生成树与并查集的核心思想贪心选边策略Kruskal 算法基于贪心思想每次选取当前最短且不会形成环的边最终得到全局最优的最小生成树。这一策略的正确性由割性质保证连通性判定通过并查集高效维护连通块信息f i n d findfind操作带路径压缩O ( α ( n ) ) O(\alpha(n))O(α(n))近似常数时间距离筛选预处理题目限制了可修建线路的最大长度先筛选有效边避免在 MST 过程中处理不可用的边不连通判定最小生成树需要恰好n − 1 n-1n−1条边连接n nn个结点若有效边不足以形成n − 1 n-1n−1条边的生成树则图不连通适用于带约束的连通性建设问题、需要在满足限制条件下求最小连接成本的优化类问题【算法标签】#普及 #生成树【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN505,MN*N,INF1e18;// N: 最大点数; M: 最大边数; INF: 无穷大intx[N],y[N];// x[i], y[i]: 第 i 座基站的坐标doublel;// l: 线路长度上限doubleans;// ans: 最小生成树的总长度intn,m;// n: 基站数量; m: 边数未使用intcur;// cur: 当前有效边数intp[N];// p[i]: 并查集中 i 的父节点doublew[N][N];// w[i][j]: 基站 i 和 j 之间的欧几里得距离structEdge// 边结构体{inta,b;// a, b: 边的两个端点doublew;// w: 边的长度booloperator(constEdgeE)const// 重载小于号用于按边长排序{returnwE.w;}}edges[M];// edges: 存储所有有效边intfind(intx)// 并查集查找操作带路径压缩{if(p[x]!x)p[x]find(p[x]);returnp[x];}doublekruskal()// Kruskal 算法求最小生成树{sort(edges1,edgescur1);// 按边长从小到大排序for(inti1;in;i)// 初始化并查集p[i]i;doubleres0;// res: 当前生成树的总长度intcnt0;// cnt: 已选入生成树的边数for(inti1;icur;i)// 遍历所有有效边{intaedges[i].a,bedges[i].b;// 边的两个端点doublewedges[i].w;// 边的长度afind(a),bfind(b);// 查找两个端点所在连通块的根if(a!b)// 如果不在同一连通块加入该边{p[a]b;// 合并两个连通块resw;// 累加边长到总长度cnt;// 边数加一}}if(cntn-1)// 如果边数不足 n-1图不连通returnINF;returnres;}signedmain(){cinnl;// 读入基站数量和线路长度上限for(inti1;in;i)// 读入每座基站的坐标cinx[i]y[i];for(inti1;in;i)// 初始化并查集p[i]i;for(inti1;in;i)// 枚举所有基站对计算距离并筛选有效边for(intji1;jn;j){// 计算欧几里得距离w[i][j]sqrt((x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j]));if(w[i][j]l)// 如果距离超过上限设为无穷大不可用w[i][j]1e18;elseedges[cur]{i,j,w[i][j]};// 加入有效边集合}doubleanskruskal();// 执行 Kruskal 算法if(ans!INF)// 如果存在最小生成树printf(%.2lf\n,ans);// 输出最小总长度保留两位小数elseprintf(Impossible\n);// 图不连通输出 Impossiblereturn0;}【运行结果】4 2 1 0 -1 -1 0 0 1 1 3.41