求助,样例过不了 qwq
(肯定全 WA 就不用说了 QAQ)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int father[4000086];
int set_x[1000086], set_y[1000086];
struct edge {
int u, v;
double w;
} e[4000086];
double dist (int x1, int y1, int x2, int y2) {
return (double)sqrt((double)(x1 - x2) * (x1 - y1) + (double)(y1 - y2) * (y1 - y2));
}
bool cmp (edge x, edge y) {
return x.w < y.w;
}
int get (int cur) {
if (father[cur] == cur) return cur;
father[cur] = get(father[cur]);
return get(father[cur]);
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &set_x[i], &set_y[i]);
int cnt = 0;
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 = dist(set_x[i], set_y[i], set_x[j], set_y[j]);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &e[++cnt].u, &e[cnt].v);
e[cnt].w = 0.0;
}
sort(e + 1, e + cnt + 1, cmp);
for (int i = 1; i <= n; i++)
father[i] = i;
double ans = 0.0;
for (int i = 1; i <= cnt; i++)
if (get(e[i].u) != get(e[i].v)) {
father[get(e[i].u)] = e[i].v;
ans += e[i].w;
}
printf("%.2f", ans);
return 0;
}