求助,总有re或mle
查看原帖
求助,总有re或mle
693551
suxinxinxin楼主2022/5/18 17:22
#include<bits/stdc++.h>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#define LL long long
#define RG register
#define DB double
#define LI inline
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
const int N = 2e7, MOD = 1e9 + 7;

LI int read()
{
	int fh = 0, s = 0; char c = getchar();
	while(c > '9' || c < '0') { if(c == '-') fh = 1; c = getchar (); }
	while(c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
	return fh ? -s : s;
}
struct node {int u, v; DB w;} e[N]; LI bool cmp (node a, node b) {return a.w < b.w;}
DB ans; int n, X[N], Y[N], cnt, fa[N], Cnt;
LI DB JS(int a, int b) {return sqrt ( pow (X[a] - X[b] , 2) + pow (Y[a] - Y[b] , 2));}
LI int find(int k) {return fa[k] == k ? k : fa[k] = find(fa[k]);}
LI void add(int a, int b) {fa[find(a)] = find(b);}
signed main()
{	
	n = read(); for (int i = 1; i <= n; ++i) fa[i] = i;
	for (int i = 1; i <= n; ++i) 
	{
		X[i] = read(), Y[i] = read();
		for (int j = 1; j < i; ++j)
		e[++cnt].u = i, e[cnt].v = j, e[cnt].w = JS(i, j);
	}
	sort (e + 1, e + 1 + cnt, cmp);
	for (int i = 1; i <= cnt; ++i)
	{
		if (find(e[i].u) != find(e[i].v))
		++Cnt, ans += e[i].w, add(e[i].u, e[i].v);
		if (Cnt == n - 1) break;
	}
	printf("%.2lf", ans);
//	cout << ans;
	return 0;
}
2022/5/18 17:22
加载中...