1 条题解
-
1赵青海 (huhe) LV 7 SU @ 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
- 上传者