题目地址：http://poj.org/problem?id=2349
输出用%f而%lf就错了，还好我机智，因为上次被坑过
选第P-S长的边
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500+5;
struct Point{int x,y;Point(int x,int y):x(x),y(y){}
};
vector<Point> points;
struct Edge{int from,to; double weight;Edge(int f,int t,double w):from(f),to(t),weight(w){}bool operator < (const Edge& e) const {return weight<e.weight;}
};
vector<Edge> edges;double dist(Point x,Point y){return hypot(x.x-y.x,x.y-y.y);
}
void initDist(int N)
{for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){double d=dist(points[i],points[j]);edges.push_back(Edge(i,j,d));}
}int p[maxn];
int find(int x) {return p[x]==x?x:p[x]=find(p[x]);
}
double Kruskal(int S,int n)
{for(int i=0;i<n;i++) p[i]=i;sort(edges.begin(),edges.end());int done=0;int m=edges.size();for(int i=0;i<m;i++){Edge e=edges[i];int u=e.from, v=e.to;double w=e.weight;int up=find(u), vp=find(v);if(up!=vp) p[up]=vp,done++;if(done==n-S) return w; //到P-S条边就结束 } return 0;
}int main()
{int T;cin>>T;while(T--){int S,P;cin>>S>>P;points.clear();for(int i=0;i<P;i++){int x,y;cin>>x>>y;points.push_back(Point(x,y));}edges.clear();initDist(P);printf("%.2f\n",Kruskal(S,P));}return 0;
}