北极通讯网络

• 这道题和我做的第一道提高课的题目（监狱那题）有点像。

• 这道题题意其实就是求在有k个联通块的情况下，每个联通块中最大的距离是多少。

• 另一个题解中描述题意描述得更形象

我们需要找到一个最小的d值,使得在删去权值大于d的所有边后,
剩下的联通块个数不超过k.

• 这里我们不需要二分来做。我们可以直接通过 kruskal 来做。因为克鲁斯卡尔的话会从最短的边开始到最长的边。（其实这是类似克鲁斯卡尔，并不是克鲁斯卡尔吧。。只是用了排序和并查集跟克鲁斯卡尔有点像。）这里当我们联通块数小于卫星数 $k$ 的时候，说明已经找到了结果。而答案就是最后一条边的长度，因为最后一条边是最大的。

• 这道题要注意数据范围，要开 $510*510$ ，因为两重循环，空间 $O(n^2)$ 。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
#define xx first
#define yy second

const int N = 1E4 * 510;
int p[N], d[N];
int n, k;
pii q[N];

struct Node
{
    int a;
    int b;
    double w;
} nodes[N];

int cnt;

double get_dist(pii i, pii j)
{
    int x = i.xx - j.xx;
    int y = i.yy - j.yy;

    return sqrt(x * x + y * y);
}

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

bool cmp(Node a, Node b)
{
    return a.w < b.w;
}

int main()
{
    cin >> n >> k;

    for (int i = 0; i < n; i ++ ) cin >> q[i].xx >> q[i].yy;

    // 初始化nodes
    for (int i = 0; i < n; i ++ )
        for (int j = i + 1; j < n; j ++ )
            nodes[cnt ++ ] = {i, j, get_dist(q[i], q[j])};

    // kruskal
    sort(nodes, nodes + cnt, cmp);
    for (int i = 0; i <= n; i ++ ) p[i] = i;

    // n块
    int kuai = n;
    double res = -1;
    for (int i = 0; i < cnt; i ++ )
    {
        if (kuai <= k) break;

        int a = nodes[i].a, b = nodes[i].b;
        double w = nodes[i].w;

        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            kuai -- ;
            res = w;
            p[pa] = pb;
        }
    }

    printf("%.2lf", res);

    return 0;
}