题解 | #Freckles#Kruskal、并查集

#include <bits/stdc++.h>

using namespace std;

struct Spot {
    float x;
    float y;

    Spot(float _x, float _y) {
        x = _x;
        y = _y;
    }
};

struct Edge {
    int a;
    int b;
    double length;

    Edge(int _a, int _b, double _length) {
        a = _a;
        b = _b;
        length = _length;
    }
};

bool compare(Edge lhs, Edge rhs) {
    if (lhs.length < rhs.length) {
        return true;
    } else {
        return false;
    }
}

int father[1001];

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

int FindFather(int u) {
    if (u == father[u]) {
        return u;
    } else {
        father[u] = FindFather(father[u]);
        return father[u];
    }
}

void UnionSet(int u, int v) {
    int u_root = FindFather(u);
    int v_root = FindFather(v);
    father[v_root] = u_root;
}

void Distance(vector<Spot>& spotVec, vector<Edge>& edgeVec, int a, int b) {
    double length = pow(pow(spotVec[a].x - spotVec[b].x,
                            2) + pow(spotVec[a].y - spotVec[b].y, 2), 0.5);
    Edge e(a, b, length);
    edgeVec.push_back(e);
}


//kruskal
double Kruskal(vector<Edge>& edgeVec, int n) {
    double distAll = 0;
    int edgeCount = 0;
    InitSet(n);
    sort(edgeVec.begin(), edgeVec.end(), compare);
    for (int i = 0; i < edgeVec.size(); ++i) {
        Edge curE = edgeVec[i];
        if (FindFather(curE.a) != FindFather(curE.b)) {
            UnionSet(curE.a, curE.b);
            distAll += curE.length;
            ++edgeCount;
            if (n - 1 == edgeCount) {
                break;
            }
        }
    }
    return distAll;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<Spot> spotVec;
    vector<Edge> edgeVec;
    for (int i = 0; i < n; ++i) {
        float x;
        float y;
        scanf("%f%f", &x, &y);
        Spot p(x, y);
        spotVec.push_back(p);
        //计算出任意两点间的距离
        for (int j = 0; j < spotVec.size(); ++j) {
            for (int k = 1; k < spotVec.size(); ++k) {
                Distance(spotVec, edgeVec, j, k);
            }
        }
    }
    //Kruskal
    printf("%.2f", Kruskal(edgeVec, n));
    return 0;
}