企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定n nn个基站的二维坐标和一个距离上限l ll，只有当两基站间欧几里得距离≤ l \leq l≤l时才能修建线路。要求使所有基站两两连通的最小线路总长度，若无法连通则输出Impossible。这是一个**最小生成树（MST）**问题，核心在于从所有可修建线路中选取总长度最小且能连接所有基站的边集。

2. 算法选择：

   • Kruskal 算法：将所有有效边按长度排序，用并查集维护连通性，贪心选取不形成环的最短边
   • 欧几里得距离筛选：先计算所有点对距离，仅保留≤ l \leq l≤l的边作为候选边

3. 关键步骤：

   • 读入数据：读取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-1<n−1，则图不连通
   • 输出结果：若连通输出总长度（保留两位小数），否则输出Impossible

4. 时间/空间复杂度：

   • 时间复杂度：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)，存储所有有效边

5. 最小生成树与并查集的核心思想：

   • 贪心选边策略：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条边的生成树，则图不连通
   • 适用于带约束的连通性建设问题、需要在满足限制条件下求最小连接成本的优化类问题

【算法标签】

#普及 #生成树

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=505,M=N*N,INF=1e18;// 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<(constEdge&E)const// 重载小于号，用于按边长排序{returnw<E.w;}}edges[M];// edges: 存储所有有效边intfind(intx)// 并查集查找操作，带路径压缩{if(p[x]!=x)p[x]=find(p[x]);returnp[x];}doublekruskal()// Kruskal 算法求最小生成树{sort(edges+1,edges+cur+1);// 按边长从小到大排序for(inti=1;i<=n;i++)// 初始化并查集p[i]=i;doubleres=0;// res: 当前生成树的总长度intcnt=0;// cnt: 已选入生成树的边数for(inti=1;i<=cur;i++)// 遍历所有有效边{inta=edges[i].a,b=edges[i].b;// 边的两个端点doublew=edges[i].w;// 边的长度a=find(a),b=find(b);// 查找两个端点所在连通块的根if(a!=b)// 如果不在同一连通块，加入该边{p[a]=b;// 合并两个连通块res+=w;// 累加边长到总长度cnt++;// 边数加一}}if(cnt<n-1)// 如果边数不足 n-1，图不连通returnINF;returnres;}signedmain(){cin>>n>>l;// 读入基站数量和线路长度上限for(inti=1;i<=n;i++)// 读入每座基站的坐标cin>>x[i]>>y[i];for(inti=1;i<=n;i++)// 初始化并查集p[i]=i;for(inti=1;i<=n;i++)// 枚举所有基站对，计算距离并筛选有效边for(intj=i+1;j<=n;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]};// 加入有效边集合}doubleans=kruskal();// 执行 Kruskal 算法if(ans!=INF)// 如果存在最小生成树printf("%.2lf\n",ans);// 输出最小总长度，保留两位小数elseprintf("Impossible\n");// 图不连通，输出 Impossiblereturn0;}

【运行结果】

4 2 1 0 -1 -1 0 0 1 1 3.41