题目描述
某国有 n 个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。
修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
政府审批的规则如下：
一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。
当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。
你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。
输入格式
第一行一个整数 n，表示城市的数量。（n≤5000）
以下 n 行，每行两个整数 x 和 y，表示一个城市的坐标。（−106≤x,y≤106）
输出格式
一个实数，四舍五入保留两位小数，表示公路总长。（保证有唯一解）
输入输出样例
输入 #1复制运行
4
0 0
1 2
-1 2
0 4
输出 #1复制运行
6.47
说明/提示
修建的公路如图所示：
Prim 算法的隐式图应用
1. 题目背景与分析
题目模型：
给定平面上N个点的坐标 (x, y)，这些点之间任意两个都可以直接相连，连接的代价是它们之间的欧几里得距离。要求将所有点连通，且总代价最小。
题目陷阱解析：
题目描述中提到了“每轮选择最近城市申请”、“成环否决最短边”等复杂的规则。其实，这些规则描述的过程，本质上就是Borůvka算法或Kruskal 算法构造最小生成树的过程。
无论描述多么花哨，这道题的核心任务非常明确：求完全图的最小生成树 (MST)。
2. 算法选型：Prim vs Kruskal
在做这道题时，算法的选择至关重要：
-
数据规模：N<=5000。
-
图的性质：这是一个完全图（任意两点间都有边）。边数 M=N*(N-1)/2约等于1.25*10^7。
对比分析：
Kruskal算法：
-
复杂度：O(M log M)。
-
计算量：1.25*10^7*log(10^7)约等于3*10^8，有超时风险。
-
空间风险：存储10^7条边需要大量内存，极易 MLE (超内存)。
Prim 算法 (朴素版)：
-
复杂度：O(N^2)。
-
计算量：5000^2 = 2.5*10^7，稳过。
-
空间优势：不需要把边存下来，只需要存储N个点的坐标。
结论：本题只能用 Prim算法，且必须采用不存边的隐式图方式。
3. 核心逻辑：隐式图Prim
由于边数太多，我们无法预先计算好所有边存入邻接矩阵。我们采取“随用随算”的策略：
距离计算：当Prim算法需要用到节点i和节点j的距离时，利用勾股定理sqrt(x_i-x_j)^2 + (y_i-y_j)^2现场计算。
流程：
-
初始化dis数组为无穷大。
-
循环N次，每次寻找一个距离当前生成树集合最近的点p。
-
将p加入集合，累加结果。
-
关键点：用点p的坐标去尝试更新所有其他未入队点j的 dis[j]。
4. 完整代码实现
//prim+不存图，边权直接随时计算
#include <iostream>
#include <cstring>//memset
#include <cmath>//对应pow
using namespace std;
int x;
double dis[5100];//每座城市到起点的距离
struct node{
double x;//横坐标
double y;//纵坐标
}n[5100];//保存所有城市坐标
const double inf=1e16;
double sum;//最小生成树长度（公路总长度）
int vis[5100];//标记每个城市是否加入城市联盟
void prim(int s){
dis[s]=0;//起点到自己距离为0
//要把所有x座城市都连接起来，每次找还未加入城市联盟且
//距离集合（城市联盟）最近的城市
for(int i=1;i<=x;i++){
int p=0;
for(int j=1;j<=x;j++){
//每次找还未加入城市联盟且距离集合（城市联盟）最近的城市
if(vis[j]==0 && dis[p]>dis[j]){
p=j;
}
}
//如果已经无城市可以加入城市联盟 就退出
if(p==0 || dis[p]>1e16) break;
vis[p]=1;//否则就标记加入联盟
sum+=dis[p];
//然后用p点去更新所有未加入联盟的点到联盟的距离（因为边可以自己加）
for(int j=1;j<=x;j++){
//如果j点经p点到达城市联盟比原本到达城市联盟的距离小
//就更新该距离
double juli=sqrt(pow(n[j].x-n[p].x,2)+pow(n[j].y-n[p].y,2));//j点到p点的距离
if(vis[j]==0 && dis[j]>juli){
dis[j]=juli;
}
}
}
}
int main(){
cin>>x;//x座城市
for(int i=0;i<=x;i++) dis[i]=1e17;//初始化每个城市到起点距离为无穷
for(int i=1;i<=x;i++){
cin>>n[i].x>>n[i].y;
}
prim(1);//因为保证有唯一解 所以从任何一个点进去都可以
printf("%.2lf",sum);
return 0;
}
5. 易错点总结
数据类型与精度：
-
坐标和距离计算必须全程使用 double。虽然坐标10^6平方后在long long范围内，但在开根号 (sqrt) 后变成了浮点数。
-
输出时请严格按照题目要求使用 printf("%.2lf",sum) 或fixed<< setprecision(2)。
无穷大的设定与比较（重中之重）：
-
数值设定：两点间最大距离约2.8*10^6，INF建议设为1e17或更大，保证远超实际距离。
-
初始化陷阱：绝对不能使用 memset(dis, 0x3f, …)。0x3f 是针对 int 的位操作技巧，作用于double会导致数据变成极小的乱码。必须使用 for 循环手动赋值 dis[i]=1e17。
-
判定方式：在判断“是否找到了有效点”或“是否连通”时，不要使用 ==（如 if(dis[p]==INF)）。由于浮点数运算存在微小误差，且为了逻辑安全，应当使用范围比较（如 if(dis[p]>1e16)）来判定是否为不可达状态。
内存限制：
千万不要尝试开 double g[5000][5000] 的邻接矩阵。这需要约 200MB 内存，大部 分题目限制 128MB，会导致MLE(内存超限)。必须使用本题解中的隐式图（现场计算距 离）方法。
