题目描述
某国有 n 个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。
修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
政府审批的规则如下：
- 如果两个或以上城市申请修建同一条公路，则让它们共同修建；
- 如果三个或以上的城市申请修建的公路成环。如下图，A 申请修建公路 AB，B 申请修建公路 BC，C 申请修建公路 CA。则政府将否决其中最短的一条公路的修建申请；
- 其他情况的申请一律同意。
一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。
当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。
你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。
输入格式
第一行一个整数 n，表示城市的数量。\(（n≤5000）\)
以下 n 行，每行两个整数 \(x\) 和 \(y\)，表示一个城市的坐标。\(（−10^6≤x,y≤10^6）\)
输出格式
一个实数，四舍五入保留两位小数，表示公路总长。（保证有唯一解）
输入输出样例
输入 #1复制运行
4
0 0
1 2
-1 2
0 4
输出 #1复制运行
6.47
说明/提示
修建的公路如图所示：
算法分析
首先，不管它什么破烂规则，它们都是迷惑人的，乍一看很复杂，但当你看到成环和最短的时候，就可以得出一个结论：用最小生成树！那么下一个难题就是最小生成树有两个算法，kruskal和prim，但是到底用哪个呢？我们分析一下复杂度，请看：
kruskal
首先因为kruskal需要对权值排序，而排序的复杂度为\(mlogm\)，\(m\)为边数，因为题中使用坐标表示的，所以边数为\(n^2\)，\(m\)最大为25000000，时间复杂度肯定会爆，所以不行。
prim
prim的时间复杂度是\(n^2\)，完全可以接受，因为prim在算的过程中不需要提前存边，所以只要等需要的时候O(1)查询两点之间的距离就行了。
回到正文
经过我一顿废话，得出了用prim，当然A掉这道题后，我也用kruskal做了一遍，得了60分，剩下4个是MLE。
代码环节
首先向我们走来的是kruskal的60分做法：
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;double z;
};
bool cmp(node a,node b){return a.z<b.z;
}
int n;
int fa[5005];
vector<node> a;
long long t1[5005];
long long t2[5005];
double sum = 0;
int find(int x){//找祖先if(fa[x]==x){return x;}else{return fa[x] = find(fa[x]);//路径压缩}
}
void kruskal(){int cnt = 0;sort(a.begin(),a.end(),cmp);//对边权排序for(auto i : a){int x = find(i.x);int y = find(i.y);if(x!=y){//不再同一连通块中fa[x] = y;sum+=i.z;cnt++;if(cnt==n-1){//所有城市都合并成一个城市了return ;}}}
}
int main(){cin>>n;for(int i = 1; i<=n; i++){fa[i] = i;//并查集初始化cin>>t1[i]>>t2[i];//输入坐标}//预处理两点间的距离for(int i = 1; i<=n; i++){for(int j = i+1; j<=n; j++){double t = sqrt((t1[i]-t1[j])*(t1[i]-t1[j])+(t2[i]-t2[j])*(t2[i]-t2[j]));a.push_back(node{i,j,t});a.push_back(node{j,i,t});}}kruskal();//调用函数printf("%.2lf",sum);//输出答案，别忘了保留两位小数return 0;
}
经过一个错误代码的展示，接着就是激动人心的AC代码—————之前的坑点说明环节，这次坑点有两个：
- 由于x和y的差值很大，所以要初始化成一个极大值，INT_MAX也不行。
- 因为边数很大，所以不能预处理边权，要手动写个函数O(1)算距离
最后就是激动人心的AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
long long t1[5005];
long long t2[5005];
double b[5005];
bool vis[5005];
double sum = 0;
double get(int x,int y){//算距离函数double t = (t1[x]-t1[y])*(t1[x]-t1[y])+(t2[x]-t2[y])*(t2[x]-t2[y]);//标准算两点之间直线距离的方法return sqrt(t);
}
void prim(){b[1] = 0.0;//起点制0for(int i = 1; i<=n; i++){double mn = 1e20;//初始化成极大值int pos;for(int j = 1; j<=n; j++){if(vis[j]==0 && b[j]<mn){//找最小值mn = b[j];pos = j;}}vis[pos] = 1;//标记sum+=b[pos];//加上边权for(int j = 1; j<=n; j++){b[j] = min(b[j],get(pos,j));//取最小值}}
}
int main(){cin>>n;for(int i = 1; i<=n; i++){b[i] = 1e20;//初始化成极大值cin>>t1[i]>>t2[i];//输入坐标}prim();//调用函数printf("%.2lf",sum);//输出答案return 0;
}
到这里这道题就完美的AC了，请点个赞再走吧。