1 条题解

  • 1
    @ 2021-10-16 17:09:49
    /*****************************************
    备注:
    ******************************************/
    #include <queue>
    #include <math.h>
    #include <stack>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    #define LL long long
    const int N = 4e6 + 10;
    const int INF = 0x3f3f3f3f;
    struct node
    {
    	int x, y;
    	double num;
    }p[N];
    int n , m , a[1000];
    double x[N] , y[N];
    inline double calc(double x1 , double y1 ,double x2 , double y2)
    {
    	return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
    }
    void init()
    {
    	for(int i = 0; i <= n ; i++)
    		a[i] = i;
    }
    int fa(int x)
    {
    	if(x == a[x])	return x;
    	return a[x] = fa(a[x]);
    }
    bool cmp(node xx , node yy)
    {
    	return xx.num < yy.num;
    }
    int main()
    {
    	cin >> n >> m;
    	init();
    	int len = 0;
    	for(int i = 1 ; i <= n ; i++)
    	{
    		cin >> x[i] >> y[i];
    		for(int j = 1 ; j < i ; j++)
    		{
    			p[len].x = i , p[len].y = j;
    			p[len++].num = calc(x[i],y[i] , x[j] , y[j]);
    		}
    	}
    	sort(p,p+len,cmp);
    	int sum = 0;
    	while(m--)
    	{
    		int xx,yy;
    		cin >> xx >> yy;
    		xx = fa(xx);
    		yy = fa(yy);
    		if(xx != yy)
    		{
    			a[xx] = yy;
    			sum++;
    		}
    	}
    	double ans = 0;
    	for(int i = 0 ; i < len ; i++)
    	{
    		int xx = p[i].x , yy = p[i].y;
    		xx = fa(xx) , yy = fa(yy);
    		if(xx != yy)
    		{
    			a[xx] = yy;
    			sum++;
    			ans += p[i].num;
    			
    		}
    		if(sum == n-1)
    			break;
    	}
    	printf("%.2lf\n",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    1328
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    46
    已通过
    12
    上传者