正确AC代码:

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 520, M = N * N / 2;
int x[N], y[N];
int p[N];

struct edge
{
    int a;
    int b;
    double w;
}e[M];

int n, m, k;

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

double dis(int i, int j)
{
    int dx = x[i] - x[j], dy = y[i] - y[j];
    return sqrt(dx * dx + dy * dy);
}

bool cmp(const edge &a, const edge &b)
{
    return a.w < b.w;
}

int main()
{
    cin >>k >>n;
    
    for(int i = 0; i < n; i ++) cin >>x[i] >>y[i];
    
    for(int i = 0; i < n; i ++)
        for(int j = i + 1; j < n; j ++)
            e[m ++] = {i, j, dis(i, j)};
    
    sort(e, e + m, cmp);
    
    for(int i = 0; i < n; i ++) p[i] = i;
    
    int cnt = n; double ans = 0;
    for(int i = 0; i < m; i ++)
    {
        if(cnt <= k) break;
        
        int a = e[i].a, b = e[i].b; double w = e[i].w;
        
        if(find(a) == find(b)) continue;
        
        p[find(b)] = find(a);
        cnt --, ans = w;
    }
    printf("%.2lf\n", ans);
    return 0;
}

可以被特判hack但AC的代码:

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 520, M = N * N / 2;
int x[N], y[N];
int p[N];

struct edge
{
    int a;
    int b;
    double w;
}e[M];

int n, m, k;

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

double dis(int i, int j)
{
    int dx = x[i] - x[j], dy = y[i] - y[j];
    return sqrt(dx * dx + dy * dy);
}

bool cmp(const edge &a, const edge &b)
{
    return a.w < b.w;
}

int main()
{
    cin >>k >>n;
    
    for(int i = 0; i < n; i ++) cin >>x[i] >>y[i];
    
    for(int i = 0; i < n; i ++)
        for(int j = i + 1; j < n; j ++)
            e[m ++] = {i, j, dis(i, j)};
    
    sort(e, e + m, cmp);
    
    for(int i = 0; i < n; i ++) p[i] = i;
    
    int cnt = n;
    for(int i = 0; i < m; i ++)
    {
        int a = e[i].a, b = e[i].b;
        
        if(find(a) == find(b)) continue;
        
        p[find(b)] = find(a);
        cnt --;
        
        if(cnt <= k)
        {
            printf("%.2lf\n", e[i].w);
            break;
        }
    }
    return 0;
}

特判是:

输入 3 3

10 10

10 0

30 0

输出

10.00

标准答案

0.00