学步园

此题求距离时直接平方会爆int。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}

struct edge {
    int x, y;
    double v;
} e[1000001];
int n, m, cnt, tot, x[1001], y[1001], fa[1001];
bool mp[1001][1001];
double ans;

inline bool cmp(edge a, edge b) {
    return a.v < b.v;
}

inline int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline long long sqr(int x) {
    return (long long) x*x;
}

inline double dis(int a, int b) {
    return sqrt(sqr(x[a] - x[b]) + sqr(y[a] - y[b]));
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        x[i] = read();
        y[i] = read();
    }
    for (int i = 1; i <= m; i++) {
        int a = find(read()), b = find(read());
        fa[a] = b;
    }
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) {
            e[++cnt] = (edge){i, j, dis(i, j)};
        }
    sort(e + 1, e + cnt + 1, cmp);
    for (int i = 1; i <= cnt; i++) {
        int p = find(e[i].x), q = find(e[i].y);
        if (p != q) {
            fa[p] = q;
            ans += e[i].v;
            tot++;
            if (tot == n - 1)break;
        }
    }
    printf("%.2lf", ans);
    return 0;
}