学步园

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 105
#define MAXM 5060
 
struct Point{
    double x, y;
};
Point p[MAXN];
struct Edge{
    int u, v;
    double w;
};
Edge edges[MAXM];
int parent[MAXN];
int N, cnt;
 
bool cmp(const Edge& a, const Edge& b) {
    return a.w < b.w;
}
 
void init() {
    memset(parent, -1, sizeof(parent));
}
 
int find(int x) {
    int s;
    for(s = x; parent[s] >= 0; s = parent[s]);
    return s;
}
 
void Union(int R1, int R2) {
    int r1 = find(R1);
    int r2 = find(R2);
    if(parent[r1] > parent[r2]) {
        parent[r2] = parent[r1] + parent[r2];
        parent[r1] = r2;
    } else {
        parent[r1] = parent[r2] + parent[r1];
        parent[r2] = r1;
    }
}
 
void kruskal() {
    init();
    int u, v, count = 0;
    double sum = 0;
    for(int i = 0; i < cnt; ++ i) {
        u = edges[i].u;
        v = edges[i].v;
        if(find(u) != find(v)) {
            Union(u, v);
            sum += edges[i].w;
            count++;
        }
        if(count >= N -1) {
            break;
        }
    }
    printf("%.2lf\n", sum);
}
 
int main() {
    freopen("poj2560.txt", "r", stdin);
    while(scanf("%d", &N) != EOF) {
        for(int i = 0; i < N; ++ i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        cnt = 0;
        for(int i = 0; i < N; ++ i) {
            for(int j = i + 1; j < N; ++ j) {
                edges[cnt].u = i;
                edges[cnt].v = j;
                edges[cnt++].w = sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
            }
        }
        sort(edges, edges + cnt, cmp);
        kruskal();
    }
    return 0;
}