最小生成树做法
之 Kruskal
算法流程（详细分析请看代码注释）：
1. 初始化并查集
并查集模板不过多解释，还不懂请参阅并查集 - OI Wiki 。
每个节点的祖先最开始都是自己。
还有 $\rm{find}$ 函数也一并写了。
int p[N]; //p数组存的是每个节点的祖先，N 即数据范围，保证能存下所有数据
inline int find(int x){ //习惯加上 inline
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
//...此处省略中间部分
for(int i = 1; i <= n; ++i) p[i] = i; //每个节点的祖先初始化为自己
2. 读入每个点的坐标
用两个数组 x [ ] , y [ ] x[], y[] x[],y[] 表示每个点的横纵坐标即可。
Code
int x[N], y[N];
//...此处省略
for(int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]);
3. 算出每两个点之间的距离
众所周知， 两点 A ( x 1 , y 1 ) A(x_1, y_1) A(x1,y1) , B ( x 2 , y 2 ) B(x_2, y_2) B(x2,y2) 之间的距离计算公式是：
d i s = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 dis = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} dis=(x1−x2)2+(y1−y2)2
So， 用一个函数来算，代码如下。
Code
inline double get_dis(int x, int y, int _x, int _y){
//因为定义 y1 容易引起冲突，所以个人习惯命名成这样
return sqrt((double)(x - _x) * (x - _x) + (double)(y - _y) * (y - _y));
}
4. 只存边，用一个结构体即可搞定。
Code
int cnt; //cnt 表示边的数量
struct Edge{
int a, b;
double w;
//表示在 部落a 与 部落b 之间的距离为 w ，也就是 a, b 之间有一条权值为 w 的边
//注意 w 是 double 类型
bool operator < (const Edge &A) const{ //由于需要排序，先重定义一下 <
return w < A.w;
}
}e[M];
//...此处省略
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
e[++cnt] = {i, j, get_dis(x[i], y[i], x[j], y[j])};
//在点 i, j 之间创建一条边
5. 对边进行排序，直接调用 s o r t sort sort 函数 （偷懒的喜悦）
Code
sort(e + 1, e + cnt + 1); //应该没什么好说的了...
6. Kruskal核心部分
简单说一下，更详细了解可参阅最小生成树 - OI Wiki。
定义 n u m num num 表示当前部落数，初始化为 n n n。
从小到大依次枚举每条边。
如果两端点不在一个集合内，就将他们合并，同时 n u m − − num-- num−−。
如果合并完后发现 n u m num num 与 k k k 相等了，就输出下一条端点需要合并的边的长度（权值）。
Code
int num = n;
for(int i = 1; i <= cnt; ++i){
int pa = find(e[i].a), pb = find(e[i].b);
//找祖先判断是否在同一集合内
if(pa != pb){ //不在一个集合内
if(num == k){
printf("%.2lf\n", e[i].w); //保留两位小数
//由于要输出下一条，就直接把判断放到最前面就可以了。
return 0;
}
p[pa] = pb; //合并
--num; //部落数-- （习惯写成 --num 的形式）
}
}
Finally——完整 Code
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010, M = N * N;
//数据范围 10^3，M 是边的个数，最大为 N * N
int n, k;
int x[N], y[N];
int p[N], cnt;
struct Edge{
int a, b;
double w;
bool operator < (const Edge &A) const{
return w < A.w;
}
}e[M];
inline int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
inline double get_dis(int x, int y, int _x, int _y){
return sqrt((double)(x - _x) * (x - _x) + (double)(y - _y) * (y - _y));
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) p[i] = i;
for(int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
e[++cnt] = {i, j, get_dis(x[i], y[i], x[j], y[j])};
sort(e + 1, e + cnt + 1);
int num = n;
for(int i = 1; i <= cnt; ++i){
int pa = find(e[i].a), pb = find(e[i].b);
if(pa != pb){
if(num == k){
printf("%.2lf\n", e[i].w);
return 0;
}
p[pa] = pb;
--num;
}
}
return 0;
}
吸氧 135 m s 135ms 135ms
蒟蒻写的很详细了。
请多多支持。