不知道为啥错了,10分,开了long long也是10分
查看原帖
不知道为啥错了,10分,开了long long也是10分
464528
见贤思齐_Seakies楼主2022/4/29 15:11
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 9;
struct Node {
	int x, y;
} a[MAXN];
struct Edge {
	int u, v;
	double w;
} e[MAXN];
int n, m, cnt;
double ans;
double dis(int u, int v) {
	return (double)(sqrt((double)(a[u].x - a[v].x) * (a[u].x - a[v].x) + (double)(a[u].y - a[v].y) * (a[u].y - a[v].y)));
}
int fa[MAXN];
void init() {
	for (int i = 1; i <= n; i++) 
		fa[i] = i;
}
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool cmp(Edge x, Edge y) {
	if (x.w == y.w) return x.u < y.u;
	return x.w < y.w;
}
void kruskal() {
	int sum = 0;
	init();
	sort(e + 1, e + cnt + 1, cmp);
	for (int i = 1; i <= cnt; i++) {
		int x = e[i].u, y = e[i].v;
		if (find(x) != find(y)) {
			sum++;
			ans += e[i].w;
			fa[find(y)] = find(x);
		}
		if (sum == n - 1) return;
	}
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i].x, &a[i].y);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			e[++cnt].u = i, e[cnt].v = j, e[cnt].w = (double)dis(i, j);
		}
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &e[++cnt].u, &e[cnt].v);
		e[cnt].w = 0.0;
	}
	kruskal();
	printf("%.2lf\n", ans);
	return 0;
}
2022/4/29 15:11
加载中...