题目描述
某国有 n 个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。
修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
政府审批的规则如下：
- 如果两个或以上城市申请修建同一条公路，则让它们共同修建；
- 如果三个或以上的城市申请修建的公路成环。如下图，A 申请修建公路 AB，B 申请修建公路 BC，C 申请修建公路 CA。则政府将否决其中最短的一条公路的修建申请；
- 其他情况的申请一律同意。
一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。
当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。
你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。
输入格式
第一行一个整数 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(内存超限)。必须使用本题解中的隐式图（现场计算距 离）方法。
)
