样例正确,没有分 第一组数据是和样例一样吗? 第一组输出的是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;
}