没有分?
查看原帖
没有分?
319003
肉包铁1810楼主2021/2/23 16:04

样例正确,没有分 第一组数据是和样例一样吗? 第一组输出的是4.00

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1005, M = 1005;
int n, m, eid;
int fa[N];
struct point {
	int x, y;
} P[N];
struct edge {
	int u, v;
	double dist;
} E[M * 2];
double juli(int x, int y, int a, int b) {
	return sqrt((a - x) * (a - x) + (b - y) * (b - y));
}
void insert(int u, int v, double dist) {
	E[++eid].u = u;
	E[eid].v = v;
	E[eid].dist = dist;
}
bool cmp(edge l, edge r) {
	if (l.dist != r.dist) {
		return l.dist < r.dist;
	}
	return l.u < r.u;
}
void init() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
}
int get(int x) {
	if (fa[x] == x) {
		return x;
	}
	return fa[x] = get(fa[x]);
}
double Kruskal(int n, int m) {
	double ans = 0.0;
	sort(E + 1, E + m + 1, cmp);
	for (int i = 0; i < m; i++) {
		edge x = E[i];
		int u = E[i].u, v = E[i].v;
		int fu = get(u), fv = get(v);
		if (fu != fv) {
			ans += E[i].dist;
			fa[fv] = fu;
		}
	}
	return ans;
	
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> P[i].x >> P[i].y;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			double dist = juli(P[i].x, P[i].y, P[j].x, P[j].y);
			insert(i, j, dist);
		} 
	}
	init();
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		int fu = get(u), fv = get(v);
		if (fu != fv) {
			fa[fv] = fu;
		}
	}
	printf("%.2llf\n", Kruskal(n, eid));
	return 0; 
}
2021/2/23 16:04
加载中...