朴素Prim $O(n^2)$

Prim算法是更快的，因为这其实是一个稠密图。跑一遍最小生成树，然后最后对n条边排序一下就好了。sort是nlogn，总共时间复杂度比Kruskal的 $n^2logn$ 要优秀一些。而且代码会更简单。

C++ 代码

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int n, k;
int pos[505][2];
bool vis[505];
double dist[505], d[505][505], edge[505];

void prim() {
    for (int i = 1; i <= n; ++i) dist[i] = 1e5;
    dist[1] = 0.0;
    for (int i = 1; i <= n; ++i) {
        int cur = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (dist[j] < dist[cur] || cur == -1)) {
                cur = j;
            }
        }
        vis[cur] = true;
        edge[i - 1] = dist[cur];
        for (int j = 1; j <= n; ++j) {
            if (dist[j] > d[cur][j]) {
                dist[j] = d[cur][j];
            }
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> pos[i][0] >> pos[i][1];
    }

    for (int i = 1; i <= n; ++i) {
        d[i][i] = 0;
        for (int j = i + 1; j <= n; ++j) {
            d[i][j] = d[j][i] = sqrt((pos[i][0] - pos[j][0]) * (pos[i][0] - pos[j][0]) + (pos[i][1] - pos[j][1]) * (pos[i][1] - pos[j][1]));
        }
    }
    prim();
    sort(edge + 1, edge + n);
    if (n >= k) printf("%.2f\n", edge[n - k]);
    else printf("%.2f", edge[0]);
    return 0;
}