[UVa] 10034 - Freckles

Method:

Algorithm used: Kruskal's MST
Complexity: n^2
Comments: I used structures to store edge & vertex information
For using qsort() you need to modify the cmp function as mine, or something
else that means the same.

Sample Input:

7

4
6.99999999999 0.99999999999999
6.99999999999 0.99999999999999
6.99999999999 -0.99999999999999
-6.99999999999 0.99999999999999

1
0.0 0.1

3
1.0 1.0
2.0 -2.0
2.0 4.0

4
1.0 1.0
2.0 2.0
2.0 4.0
-3.0 9.0

3
1.0 1.0
2.0 2.0
2.0 4.0

4
1.0 1.0
-2.0 -2.0
2.0 -4.0
3.0 9.0

5
0.0 0.0
0.0 -0.0
0.0 -0.0
-0.0 0.0
0.0 0.0

Sample Output:

16.00

0.00

6.32

10.49

3.41

16.96

0.00

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10100
int rank[MAX], p[MAX];
char blank[MAX];

struct point {
    double x, y;
} V[MAX]={0.0,0.0};

struct edge {
    int u, v;
    double w;
} A[MAX]={0,0,0.0}, E[MAX]={0,0,0.0};

int cmp(const void *a, const void *b) {
    /*return (((struct edge*)a)->w - ((struct edge*)b)->w);*/
    if (((struct edge*)a)->w > ((struct edge*)b)->w) return 1;
    else if (((struct edge*)a)->w < ((struct edge*)b)->w) return -1;
    else return 0;
}

double dis(int u, int v) {
    return sqrt(pow(V[u].x-V[v].x,2.0)+pow(V[u].y-V[v].y,2.0));
}

void make_set(int x) {
    p[x]=x;
    rank[x]=0;
}

int find_set(int x) {
    if (x!=p[x]) {
        p[x]=find_set(p[x]);
    }
    return p[x];
}

void link(int x, int y) {
    if (rank[x]>rank[y]) {
        p[y]=x;
    } else {
        p[x]=y;
        if (rank[x]==rank[y]) {
            rank[y]=rank[y]+1;
        }
    }
}

void uni(int x, int y) {
    link(find_set(x),find_set(y));
}

int kruskal(int num_vertex, int num_edge) {

    int idx_A=0, i;

    for (i=0 ; i<num_vertex ; i++) {
        make_set(i);
    }

    qsort(E,num_edge,sizeof(struct edge),cmp);

    for (i=0, idx_A=0 ; i<num_edge ; i++) {
        if (find_set(E[i].u)!=find_set(E[i].v)) {
            A[idx_A++]=E[i];
            uni(E[i].u,E[i].v);
        }
    }

    return idx_A;

}


int input(int num_vertex) {

    int i;

    for (i=0 ; i<num_vertex ; i++) {
        scanf("%lf %lf",&V[i].x,&V[i].y);
    }

    return num_vertex;
}

int edgify(int num_vertex) {

    int i, j, k;

    for (i=0, k=0 ; i<num_vertex ; i++) {
        for (j=0 ; j<num_vertex ; j++) {
            E[k].u = i;
            E[k].v = j;
            E[k].w = dis(i,j);
            k++;
        }
    }

    return k;

}


int main() {

    int i, num_vertex, test, blanker=1;
    double sum;

    scanf("%d",&test);
    getchar();

    while (test--) {

        gets(blank);

        scanf("%d",&num_vertex);
        getchar();

        sum = 0.0;

            int num_edge = edgify(input(num_vertex));

            int tree_count = kruskal(num_vertex,num_edge);

            for (i=0; i<tree_count ; i++) {
                sum = sum + A[i].w;
            }
            if (blanker++>1) putchar('\n');
            printf("%.2lf\n",sum);
    }

    return 0;
}