<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
Kruskal算法
一眼最小生成树,有几个需要注意的地方提醒一下就行
第一,k=0和k>=n的特判,k=0和k=1的效果是一样的,没有任何村庄可以通过卫星设备通信,所以需要将k=0统一为k=1,当k>=n时,所有村庄都可以用卫星通信了,就可以直接输出0,不用做Kruskal算法
第二,选边的时候,可以直接用vector存放每条边的长度,不用借助优先队列实现,因为在Kruskal算法初始化的时候就已经把边长升序排列了,在其中选出的每条边,长度都应该是逐渐增大的
其余细节见注释
时间复杂度
$O(n^2\*log(n))$
实际边数为$n\*(n-1)/2$,相当于复杂度里边的$n^2$项
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <tuple>
#include <cmath>
#include <vector>
using namespace std;
using Edge = tuple<double, int, int>;
//Kruskal算法要用的并查集类,不用多说了
class UnionFind {
private:
vector<int> ori;
int find(int x) {
if (x != ori[x]) ori[x] = find(ori[x]);
return ori[x];
}
public:
UnionFind(int n) {
ori.resize(n + 1);
iota(ori.begin(), ori.end(), 0);
}
bool isConnected(int s, int e) {
int pr = find(s), nx = find(e);
if (pr == nx) return true;
ori[pr] = nx;
return false;
}
};
int main() {
vector<Edge> edges;
vector<double> val, ox, oy;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
UnionFind uf(n);
//可以优先给cout对象固定好浮点数输出精度
cout << fixed << setprecision(2);
//如果卫星设备的数量不小于村庄总数量,那么不用搭设无线电
if (n <= k) cout << 0.00 << endl;
else {
ox.resize(n + 1);
oy.resize(n + 1);
double dx, dy;
//输入所有位置坐标,两两求距离并作为图结构的一条边存起来
for (int i = 1; i <= n; i++) {
cin >> ox[i] >> oy[i];
for (int j = 1; j < i; j++) {
dx = ox[i] - ox[j], dy = oy[i] - oy[j];
edges.push_back({ sqrt(dx * dx + dy * dy), i, j });
}
}
//开始选边
sort(edges.begin(), edges.end());
for (auto& ed : edges) {
double v = get<0>(ed);
int s = get<1>(ed), e = get<2>(ed);
if (uf.isConnected(s, e) == false) val.push_back(v);
}
//k台卫星可以代替k-1条边,之后留下的最长边下标就是n-1-k(k=0相当于k=1,需要统一到1)
if(k == 0) k++;
cout << val[n - 1 - k] << endl;
}
return 0;
}