P201 Freckles

第一次提交时样例能通过，但是测试不通过，得到的数远大于正确结果，是因为没有计算好边的数量。直接把边数用n处理了，实际上应该是n*(n-1)/2，即每两点间有一个边。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>

using namespace std;

const int MAXN = 100;

struct freckles{
    double x;
    double y;
}points[MAXN];

struct edge{
    int from;
    int to;
    double length;
}edges[MAXN*MAXN];

int father[MAXN];
int height[MAXN];

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

void initial(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]++;
        }
    }
}

double Kruskal(int n, int edgeNumber){
    initial(n);
    double ans = 0;
    sort(edges, edges + edgeNumber, cmp);
    for(int i = 0; i < edgeNumber; i++){
        edge tmp = edges[i];
        if(find(tmp.from) != find(tmp.to)){
            Union(tmp.from, tmp.to);
            //printf("%d %d %d\n", tmp.from, tmp.to, tmp.length);
            ans += tmp.length;
        }
    }
    return ans;
}

int main(){
    int n;
    while(cin >> n){
        for(int i = 0; i < n; i++){
            cin >> points[i].x >> points[i].y;
        }
        int k = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                edges[k].from = i;
                edges[k].to = j;
                double len = pow((points[i].x-points[j].x), 2) + pow((points[i].y-points[j].y), 2);
                //printf("%d %d %.04f\n", edges[k].from, edges[k].to, len);
                edges[k].length = pow(len, 0.5);
                //printf("%d %d %.04f\n", edges[k].from, edges[k].to, edges[k].length);
                k++;
            }
        }
        double ans = Kruskal(n, n * (n - 1) / 2);
        printf("%.2lf\n", ans);
    }
}