题解 | #Freckles#

//这题注意距离计算和小数的问题即可
#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
const int maxn = 110;
using namespace std;
int father[maxn];
int height[maxn];

struct Edge {
    int from;
    int to;
    double length;
    bool operator<(const Edge& e) {
        return length < e.length;
    }
};

struct Point {
    double x, y;
    Point(double x, double y): x(x), y(y) {}
};

double distance1(Point* p1, Point* p2) {
    double dis = (p1->x - p2->x) * (p1->x - p2->x) + (p1->y - p2->y) *
                 (p1->y - p2->y);
    return sqrt(dis);
}

Edge edge[maxn * maxn];

void init(int n) {
    for (int i = 0; i <= n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x, int  y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1;
        }
    }
}

double kruskal(int n, int edgeNumber) {
    init(n);
    sort(edge, edge + edgeNumber);
    double sum = 0;
    for (int i = 0; i < edgeNumber; i++) {
        Edge current = edge[i];

        if (find(current.from) != find(
                    current.to)) { //将这条边联通不会产生回环

            Union(current.from, current.to);
            sum += current.length;
        }
    }
    return sum;

}

//3
//1.0 1.0
//2.0 2.0
//2.0 4.0

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        double x, y;
        vector<Point*> points;
        for (int i = 0; i < n; i++) {
            cin >> x >> y;
            points.push_back(new Point(x, y));
        }
        int num = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                edge[num].from = i;
                edge[num].to = j;
                edge[num].length = distance1(points[i], points[j]);
                num++;
            }
        }

        printf("%0.2f\n", kruskal(n, num));


    }
}