算法

(最小生成树) $O(n^2logn)$

很显然，每合并一条边，图中就减少一个连通块。
则i次操作之后，树中还剩下n-i个连通块。
如果图中还剩下恰好S个连通块，给每个连通块发一个卫星就行了。
而合并边的操作显然是最小生成树的流程，用Kruskal算法合并掉P-S个连通块即可。

时间复杂度分析

边的数量是$O(n^2)$级别的，所以时间复杂度近似为$O(n^2logn)$。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 510

using namespace std;

int m, n;
struct Edge{
    int x, y;
    double d;
    bool operator<(const Edge &W) const {
        return d < W.d;
    }
};
struct Points{
    int x, y;
    double operator+(const Points &W) const {
        int cx = x - W.x, cy = y - W.y;
        return sqrt(cx * cx + cy * cy);
    }
}points[maxn];
vector<Edge> e;
int p[maxn];

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void solve()
{
    e.clear();
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &points[i].x, &points[i].y);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i != j) e.push_back({i, j, points[i] + points[j]});
    sort(e.begin(), e.end());

    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int tot = 0;
    double ans = 0;
    for (Edge edge : e)
    {
        if (tot == n - m)
        {
            printf("%.2lf\n", ans);
            return;
        }

        int x = find(edge.x), y = find(edge.y);
        double w = edge.d;
        if (x != y)
        {
            p[x] = y;
            ans = max(ans, w);
            tot ++ ;
        }
    }

    printf("%.2lf\n", ans);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- ) solve();

    return 0;
}