P1265 公路修建【洛谷算法习题】-平芜编程栈

P1265 公路修建

网页链接

P1265 公路修建

题目描述

某国有n nn个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。

修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。

政府审批的规则如下：

如果两个或以上城市申请修建同一条公路，则让它们共同修建；
如果三个或以上的城市申请修建的公路成环。如下图，A 申请修建公路 AB，B 申请修建公路 BC，C 申请修建公路 CA。则政府将否决其中最短的一条公路的修建申请；
其他情况的申请一律同意。

一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。

当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。

你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。

输入格式

第一行一个整数n nn，表示城市的数量。（n ≤ 5000 n \leq 5000n≤5000）

以下n nn行，每行两个整数x xx和y yy，表示一个城市的坐标。（− 10 6 ≤ x , y ≤ 10 6 -10^6 \leq x,y \leq 10^6−106≤x,y≤106）

输出格式

一个实数，四舍五入保留两位小数，表示公路总长。（保证有唯一解）

输入输出样例 #1

输入 #1

4 0 0 1 2 -1 2 0 4

输出 #1

6.47

说明/提示

修建的公路如图所示：

解题思路

本题是最小生成树（基于 Prim 算法）的经典题型，核心是把"多轮联盟 + 申请 + 审批"看似复杂的过程，看穿为"从任一节点出发，反复选取连接当前联盟与未加入节点的最短边"的 Prim 过程；最终被批准公路的长度之和，就是该图一棵最小生成树的边权和。

1. 问题等价转化

多轮过程本质是 Prim 的多步迭代：第 1 轮每个城市申请到自己最近邻的若干条公路，被批准后形成若干"联盟"（即树的若干连通块）；下一轮中联盟被视为一个城市，重复"申请—批准—合并"。这与 Prim 算法每轮"向树外取一个最近的点"完全同构。
规则 1（共同修建）不改变总长：两个及以上城市同时申请同一条公路只是同时被批准，对总长度和联盟形态均无影响。
规则 2（环中砍最短）即禁环：当三个及以上城市申请的边形成环时，否决最短的一条。MST 不允许出现环，环中冗余的最长边一定不在 MST 中——因此砍掉环中最短边等价于保留环中最长边外侧的最短生成树形态，对最终 MST 边权无影响。
"联盟"与树扩张的等价性：每轮联盟对外部的最短距离等于"联盟内所有成员到外部节点的最小距离"，这恰是 Prim 维护的dis[j] = min(dist(j, v) | v ∈ 当前联盟)。本轮新增边即为该最小值，被批准后j jj加入联盟，扩张继续。
结论：无论规则如何演化，最终建成的"城市联盟"是一棵树，总长度就是该图最小生成树的边权；该题所求的"公路总长"就是 MST 边权和。

2. 算法实现：朴素 Prim（O ( n 2 ) O(n^2)O(n2)）

建图 + 初始化：读入n nn个城市坐标；任选一城市（取城市 1）作为起点，置dis[1]=0、其余dis[i]=INF，并令所有vis[i]=false。
外层n nn次扩张：每轮从未访问节点中选dis最小者mj，将其加入联盟：ans += dis[mj]; vis[mj]=true。
松弛更新：以新加入的mj为源，遍历所有未访问节点j jj，计算欧氏距离dist(mj, j)，若小于dis[j]则更新。
结果输出：n nn轮结束后ans即 MST 边权和，按%.2lf四舍五入输出两位小数。

3. 复杂度分析

时间复杂度：O ( n 2 ) O(n^2)O(n2)。外层n nn轮 × 内层n nn次松弛，约n 2 n^2n2次距离计算（含sqrt）；n ≤ 5000 n\le5000n≤5000时约2.5 × 10 7 2.5\times10^72.5×107次，1 秒内可接受。
空间复杂度：O ( n ) O(n)O(n)。坐标p[N][2]、距离dis[N]、访问标记vis[N]均为n nn规模。

总结

核心逻辑：多轮"联盟—审批"与 Prim 最小生成树同构，答案即 MST 边权之和。
关键操作：选当前未访问节点中dis最小者加入联盟，并以其更新所有未访问节点到联盟的距离。
效率保障：O ( n 2 ) O(n^2)O(n2)朴素 Prim 适配n ≤ 5000 n\le5000n≤5000；距离使用double存储避免先取平方再开方时的精度损失。

代码简要说明

类型与常量：typedef long long ll、ull、vvt、pll以及N/INF/M/mod均为模板残留，本题未使用，可忽略；MN=5005决定坐标、距离、访问数组的最大规模。
核心函数dist：计算两点欧氏距离并返回double；x1-x2等差值已用(double)强转，避免long long平方后溢出（约2 × 10 12 2\times10^{12}2×1012仍安全，但统一转double更稳妥）。
主函数：
- 用scanf读入n nn与各城市坐标（%lld适配long long）；
- 利用全局数组的零初始化把dis[1]留为0 00，其余dis[2..n]=INF；
- 进行n nn轮朴素 Prim：选未访问节点中dis最小者mj，ans += dis[mj]; vis[mj]=true;，再以mj更新所有未访问节点的距离；
- 用printf("%.2lf", ans)四舍五入输出两位小数。
输入输出优化：ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);配合scanf/printf混用，兼顾速度与格式精度。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll MN=5005;ll p[MN][2];doubledis[MN];boolvis[MN];doubledist(ll x1,ll y1,ll x2,ll y2){returnsqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,i,j;scanf("%lld",&n);for(i=1;i<=n;i++)scanf("%lld%lld",&p[i][0],&p[i][1]);for(i=2;i<=n;i++)dis[i]=INF;ll mj;doublemi;doubleans=0;for(i=1;i<=n;i++){mi=INF;for(j=1;j<=n;j++){if(!vis[j]&&dis[j]<mi){mj=j;mi=dis[j];}}ans+=mi;vis[mj]=true;for(j=1;j<=n;j++){doublet=dist(p[mj][0],p[mj][1],p[j][0],p[j][1]);if(t<dis[j])dis[j]=t;}}printf("%.2lf\n",ans);return0;}