POJ2560 Freckles（最小生成树）

题意分析：

给定坐标上的n个点，要求把其连接起来，计算连接起来所需要的变长之和的最小值。 Kruskal构建最小生成树。

#include <iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 10010
using namespace std;
typedef long long ll;
typedef struct Node{
    double x,y;double cost;
}node;
node l[maxn],e[maxn];
ll n,pos = 0,pa[maxn];
double ans = 0;
double getDistance(ll i, ll j) {
    return sqrt((l[i].x - l[j].x)*(l[i].x - l[j].x) + (l[i].y - l[j].y)*(l[i].y - l[j].y));
}bool cmp(node x, node y) {
    return x.cost < y.cost;
}
ll findSet(ll x) {
    if (x != pa[x]) return pa[x] = findSet(pa[x]);return pa[x];
}
bool isSame(ll x, ll y) {
    return findSet(x) == findSet(y);
}
void unionSet(ll x, ll y) {
    x = findSet(x);y = findSet(y);if (x == y) return;pa[x] = y;
}int main()
{
    std::ios::sync_with_stdio(false);cin >> n;for (int i = 0; i < n; i++) {
    cin >> l[i].x >> l[i].y;}for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
    e[pos].x=i;e[pos].y=j;e[pos].cost = getDistance(i, j);pos++;}}sort(e, e + pos, cmp);for(int i=0;i<n;i++){
    pa[i]=i;}for (int i = 0; i < pos; i++) {
    //cout<<findSet(e[i].x)<<" "<<findSet(e[i].y)<<endl;if (isSame(e[i].x, e[i].y)) continue;unionSet(e[i].x, e[i].y);ans += e[i].cost;}printf("%.2f", ans);return 0;
}