[洛谷1991]无线通讯网

思路：
考虑使用卫星替代最小生成树中最大的$s-1$条边，答案即为剩下的最大边。

#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {
    char ch;
    while(!isdigit(ch=getchar()));
    int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
inline int sqr(const int x) {
    return x*x;
}
const int N=500;
struct Point {
    int x,y;
    friend double dist (const Point a,const Point b) {
        return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
    }
};
Point p[N];
struct Edge {
    int u,v;
    double w;
    bool operator < (const Edge &another) const {
        return w<another.w;
    }
};
std::vector<Edge> e;
class DisjointSet {
    private:
        int anc[N];
        int Find(const int x) {
            return x==anc[x]?x:anc[x]=Find(anc[x]);
        }
    public:
        DisjointSet() {
            for(int i=0;i<N;i++) anc[i]=i;
        }
        bool isConnected(const int x,const int y) {
            return Find(x)==Find(y);
        }
        void Union(const int x,const int y) {
            anc[Find(x)]=Find(y);
        }
};
DisjointSet s;
int main() {
    int m=getint(),n=getint();
    for(int i=0;i<n;i++) {
        p[i].x=getint();
        p[i].y=getint();
    }
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            e.push_back((Edge){i,j,dist(p[i],p[j])});
        }
    }
    std::sort(e.begin(),e.end());
    double ans;
    for(unsigned i=0,cnt=n-m;i<e.size()&&cnt;i++) {
        int u=e[i].u,v=e[i].v;
        double w=e[i].w;
        if(s.isConnected(u,v)) continue;
        s.Union(u,v);
        ans=w;
        cnt--;
    }
    printf("%.2f",ans);
    return 0;
}