分析：使用krusal添加p-s条边就行了，因为剩下的边肯定会比已经添加的边要长，在添加的边里面选取最长的那条，也就是最后添加的那条。
************************************************************************************
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<math.h> #include<vector> using namespace std; #define maxn 505 int f[maxn]; struct node { int u, v; double len; friend bool operator < (node a, node b) { return a.len > b.len; } }; struct point{ double x, y;}p[maxn]; double Len(point a, point b) { double x = a.x - b.x; double y = a.y - b.y; double l = sqrt(x*x+y*y); return l; } int Find( int x) { if(f[x] != x) f[x] = Find(f[x]); return f[x]; } int main() { int T; scanf( " %d ", &T); while(T--) { int S, N, u, v; node s; priority_queue<node> Q; scanf( " %d%d ", &S, &N); for(s.u= 1; s.u<=N; s.u++) { f[s.u] = s.u; scanf( " %lf%lf ", &p[s.u].x, &p[s.u].y); for(s.v= 1; s.v<s.u; s.v++) { s.len = Len(p[s.u], p[s.v]); Q.push(s); } } while(Q.size() && S < N) { s = Q.top();Q.pop(); u = Find(s.u), v = Find(s.v); if(u != v) { S++; f[u] = v; } } printf( " %.2f\n ", s.len); } return 0; }