题目地址
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#include<vector>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;typedef pair<double,double> Point;
int N,p[maxn],r[maxn*maxn];
vector<Point> points;
vector<double> edge;
map<int,Point> idx;double dist(Point x,Point y){return hypot(abs(x.first-y.first),abs(x.second-y.second));
}
int getParent(int x){if(p[x]==x) return x;return p[x]=getParent(p[x]);
}
bool cmp(int i,int j){return edge[i]<edge[j];
}
double getdist(){for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){double d=dist(points[i],points[j]);edge.push_back(d);idx[edge.size()-1]=Point(i,j);}points.clear();for(int i=0;i<edge.size();i++) r[i]=i;sort(r,r+edge.size(),cmp);double ans=0;int cnt=0;for(int i=0;i<edge.size();i++){int j=r[i]; //第i条边 j int x=idx[j].first,y=idx[j].second;int xp=getParent(x),yp=getParent(y);if(xp==yp) continue;ans+=edge[j];cnt++;p[xp]=yp; if(cnt==N-1) break;}return ans;
}
int main()
{double x,y;cin>>N;for(int i=0;i<N;i++){cin>>x>>y;p[i]=i;points.push_back(Point(x,y));}printf("%.2lf\n",getdist());return 0;
}