1145. 北极通讯网络

北极的某区域共有 n 座村庄，每座村庄的坐标用一对整数 (x,y) 表示。

为了加强联系，决定在村庄之间建立通讯网络，使每两座村庄之间都可以直接或间接通讯。

通讯工具可以是无线电收发机，也可以是卫星设备。

无线电收发机有多种不同型号，不同型号的无线电收发机有一个不同的参数 d，两座村庄之间的距离如果不超过 d，就可以用该型号的无线电收发机直接通讯，d 值越大的型号价格越贵。现在要先选择某一种型号的无线电收发机，然后统一给所有村庄配备，数量不限，但型号都是 相同的。

配备卫星设备的两座村庄无论相距多远都可以直接通讯，但卫星设备是 有限的，只能给一部分村庄配备。

现在有 k 台卫星设备，请你编一个程序，计算出应该如何分配这 k 台卫星设备，才能使所配备的无线电收发机的 dd 值最小。

例如，对于下面三座村庄：

其中，||AB|=10,|BC|=20,|AC|=105≈22.36。

如果没有任何卫星设备或只有 1 台卫星设备 (k=0 或 k=1)，则满足条件的最小的 d=20，因为 A 和 B，B 和 C 可以用无线电直接通讯；而 A 和 C 可以用 B 中转实现间接通讯 (即消息从 A 传到 B，再从 B 传到 C)；

如果有 2 台卫星设备 (k=2)，则可以把这两台设备分别分配给 B 和 C ，这样最小的 d 可取 10，因为 A 和 B 之间可以用无线电直接通讯；B 和 C 之间可以用卫星直接通讯；A 和 C 可以用 B 中转实现间接通讯。

如果有 3 台卫星设备，则 A,B,C 两两之间都可以直接用卫星通讯，最小的 d 可取 0。

输入格式

第一行为由空格隔开的两个整数 n,k;

接下来 n 行，每行两个整数，第 i 行的 xi,yi 表示第 i 座村庄的坐标 (xi,yi)。

输出格式

一个实数，表示最小的 d 值，结果保留 2 位小数。

数据范围

1≤n≤500,
0≤x,y≤104,
0≤k≤100

输入样例：

3 2
10 10
10 0
30 0

输出样例：

10.00

思路：

/*
假设有给定一个d值，任意两个长度小于等于d的点，按照最小生成树的方式进行集合合并，形成m个连通块(m 棵最小生成树)，则需要m个卫星设备
即找一个最小的d值，使得将所有权值大于d的边删去，之后，整个图形的连通块的个数等于k 
Kruskal算法，按照边从小到大枚举对连通块进行合并，随着枚举的边越大，连通块的个数越小 
*/

代码：

#include 
using namespace std;typedef pair PII;
const int N = 510, M = N * N / 2 + 10;
int f[N];
int n, m, k;
double res;
vector q;
struct Edge
{int a, b;double w;bool operator<(const Edge &W) const{return w < W.w;}
} e[M];int find(int x) // 从小到大用了并查集就可以省略二分
{if (x != f[x])f[x] = find(f[x]);return f[x];
}double get_dist(PII a, PII b)
{int dx = a.first - b.first;int dy = a.second - b.second;return sqrt(dx * dx + dy * dy);
}
void kruskal()
{for (int i = 1; i <= n; i++)f[i] = i;for (int i = 1; i <= n; i++){for (int j = 1; j < i; j++)e[m++] = {i, j, get_dist(q[i], q[j])};}sort(e, e + m);int cnt = n;for (int i = 0; i < m; i++){if (cnt == k) // 剩余k个连通块break;int t1 = find(e[i].a);int t2 = find(e[i].b);if (t1 != t2){f[t1] = t2;res = e[i].w;cnt--;}}
}int main()
{cin >> n >> k;q.resize(n + 1);for (int i = 1; i <= n; i++){cin >> q[i].first >> q[i].second;}kruskal();printf("%.2lf\n", res);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！