题目链接:点击打开链接
还是很基础的最小生成树
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=105; const int Max=5005; int n,top,father[N]; struct Point { double x,y; }point[N]; struct Line { double a,b; double lenth; }line[Max]; bool cmp(Line A,Line B) { if(A.lenth<B.lenth) return true; return false; } void Init() { for(int i=0;i<=n;i++) father[i]=i; top=0; } void input() { for(int i=1;i<=n;i++) scanf("%lf%lf",&point[i].x,&point[i].y); for(int i=1;i<=n;i++)//直接枚举所有的连线进行排序. { for(int j=i+1;j<=n;j++) { line[top].a=i; line[top].b=j; line[top].lenth=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)); top++; } } } int find(int x) { if(x!=father[x]) father[x]=find(father[x]); return father[x]; } void kruscal() { double min=0; sort(line,line+top,cmp); for(int i=0;i<top;i++) { int x=find(line[i].a); int y=find(line[i].b); if(x!=y) { father[x]=y; min+=line[i].lenth; } } printf("%.2lf\n",min); } int main() { while(~scanf("%d",&n)) { Init(); input(); kruscal(); } }
1A