1 solutions

  • 0
    @ 2025-11-5 15:54:33

    C++ :

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int parent[105];
    struct lu
    {
    	int a,b;
    	double length;
    }lu[10010];
    
    struct point
    {
    	double x,y;
    	int num;
    }point[105];
    
    int root(int p)
    {
    	if(parent[p]==-1)
    		return p;
    	else return parent[p]=root(parent[p]);
    }
    
    void merge(int a,int b)
    {
    	a=root(a);
    	b=root(b);
    	parent[a]=b;
    }
    
    int cmp(const void *a,const void *b)
    {
    	struct lu *c,*d;
    	c=(struct lu *)a;
    	d=(struct lu *)b;
    	if(c->length>d->length) return 1;
    	if(c->length==d->length) return 0;
    	if(c->length<d->length) return -1;
    }
    
    void ling()
    {
    	int i,j,k;
    	for(i=0;i<105;i++)
    		parent[i]=-1;
    	for(i=0;i<10010;i++)
    	{
    		lu[i].length=0.0;
    	}
    }
    
    int main()
    {
    	//freopen("B题测试数据.txt","r",stdin);
    	//freopen("B题输出结果.txt","w",stdout);
    	int i,j,k,l,m,n;
    	double ans;
    	while(scanf("%d",&n)!=EOF)
    	{
    		ling();
    		for(i=0;i<n;i++)
    		{
    			scanf("%lf%lf",&point[i].x,&point[i].y);
    		}
    		l=0;
    		ans=0.0;
    		for(i=0;i<n;i++)
    			for(j=i+1;j<n;j++)
    			{
    				lu[l].a=i;
    				lu[l].b=j;
    				lu[l].length=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));
    				l++;
    			}
    		qsort(lu,l,sizeof(struct lu),cmp);
    		for(i=0;i<n*n;i++)
    		{
    			if(root(lu[i].a)!=root(lu[i].b))
    			{
    				merge(lu[i].a,lu[i].b);
    				ans=ans+lu[i].length;
    			}
    		}
    		printf("%.2lf\n",ans);
    	}
    	return 0;
    }
    
    • 1

    Information

    ID
    17314
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By