UVa : 10034


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

struct node {
    int start;
    int end;
    double distance;
} a [100 * 100 + 10];

struct vertex {
    double x;
    double y;
} v [100 + 10];

bool cmp (node p, node q)
{
    if ( p.distance > q.distance )
        return false;
    return true;
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);
    bool blankLine = false;

    while ( testCase-- ) {
        int n;
        scanf ("%d", &n);

        int parent [100 + 5];
        double matrix [100 + 5] [100 + 5];

        for ( int i = 0; i < 105; i++ ) {
            for ( int j = 0; j < 105; j++ ) {
                matrix [i] [j] = -1;
            }
            parent [i] = i;
        }

        for ( int i = 1; i <= n; i++ )
            scanf ("%lf %lf", &v [i].x, &v [i].y);

        for ( int i = 1; i <= n; i++ ) {
            for ( int j = 1; j <= n; j++ ) {
                if ( matrix [i] [j] == -1 ) {
                    double d = sqrt ((v [i].x - v [j].x) * (v [i].x - v [j].x) + (v [i].y - v [j].y) * (v [i].y - v [j].y));
                    matrix [i] [j] = matrix [j] [i] = d;
                }
            }
        }

        int length_a = 0;

        for ( int i = 1; i <= n; i++ ) {
            for ( int j = i + 1; j <= n; j++ ) {
                a [length_a].start = i;
                a [length_a].end = j;
                a [length_a].distance = matrix [i] [j];
                length_a++;
            }
        }

        sort (a, a + length_a, cmp);

        double output = 0;
        int c = 1;
        for ( int i = 0; i < length_a && c < n; i++ ) {
            if ( parent [a [i].start] != parent [a [i].end] ) {
                c++;
                output += a [i].distance;
                for ( int j = 1; j <= n; j++ ) {
                    if ( parent [a [i].end] == parent [j] && a [i].end != j )
                        parent [j] = parent [a [i].start];
                }
                parent [a [i].end] = parent [a [i].start];
            }
        }

        //printf ("c :>> %d\n", c);

        if ( blankLine )
            printf ("\n");
        blankLine = true;
        printf ("%.2lf\n", output);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

// common mistake : 
/*
update parent carefully 
do not use more edge
*/
Advertisements

2 thoughts on “UVa : 10034

  1. @Rahat
    when there are 5 nodes then we need exactly 4 edges to connect them
    here variable ‘c’ is actually represented the number of edges i have used so far
    so until ‘c’ is less then ‘n’ the loop should continue

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s