题目描述
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn) 北极的某区域共有座村庄，每座村庄的坐标用一对整数表示，其中。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。
不同型号的无线电收发机有一个不同的参数，两座村庄之间的距离如果不超过就可以用该型号的无线电收发机直接通讯，值越大的型号价格越贵。
拥有卫星设备的两座村庄无论相距多远都可以直接通讯。
现在有台卫星设备，请你编写一个程序，计算出应该如何分配这台卫星设备，才能使所有的无线电收发机的值最小，并保证每两座村庄之间都可以直接或间接地通讯。
输入
第一行包括两个整数、，表示村庄的数量和卫星设备的数量。
之后的行，输入，，表示第个村庄的坐标。
输出
输出一个数，代表的最小值。输出保留两位小数。
样例输入
3 2
10 10
10 0
30 0样例输出
10.00思路
给一个无向图, 为了让所有点连通, 给你k个卫星站, 任意两个卫星站之间可以直接通讯, 距离为0, 但卫星站的数量不一定够用, 有一部分之间是无法通过卫星相连, 故又让你选一种型号的无线电收发机, 给无法通过卫星相连的村庄。无线电收发机不同型号有不同的范围d, 输出让整个图连通所能用的最小的d。
给了我们两个有关条件, 卫星站和无线电, 假设每个村庄都有无线电, 村庄之间距离小于等于d的就会自行连接到一起, 而卫星站的作用就是连接这些分散的连通块。即有多少个连通块就需要用多少个卫星。
显然可以得出一个单调性, d值越大, 连通块数量越小, 卫星数量越小。由此可以用二分d值, dfs求连通块数量, 可以在 的复杂度下解决。
也可以用Kruscal算法, 在枚举最小边时连通块数量最大, 每连接不在一通块内部的一对点, 就会让总连通块数量减一, 当减到 时就停下来, 输出当前的权值即可。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;
pair<double, double> g[550];
const int N = 250100;
struct Edge
{
int a, b;
double w;
bool operator<(const Edge &W) const
{
return w < W.w;
}
} e[N];
int n, m, cnt;
int f[550];
double get_dist(int i, int j)
{
double x = g[i].first - g[j].first;
double y = g[i].second - g[j].second;
return sqrt(x * x + y * y);
}
int find(int x) { return f[x] == x ? f[x] : find(f[x]); }
int main()
{
cout << fixed << setprecision(2);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> g[i].first >> g[i].second;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
e[cnt++] = {i, j, get_dist(i, j)};
sort(e, e + cnt);
int res = n;
for (int i = 1; i <= n; i++)
f[i] = i;
for (int i = 0; i < cnt; i++)
{
int a = find(e[i].a), b = find(e[i].b);
double w = e[i].w;
if (a != b)
{
res--;
f[b] = a;
if (res == m)
{
cout << w << endl;
break;
}
}
}
return 0;
}