题目地址：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; }
