UVa : 11631 (Dark roads)


// http://uva.onlinejudge.org/external/116/11631.html

// @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 <cmath>
#define N 1000000
using namespace std;

struct node {
    int start;
    int end;
    int dist;
} a [200000 + 10];

int parent [200000 + 10];
int size [200000 + 10];

bool cmp (node x, node y)
{
    if ( x.dist < y.dist ) return true;
    return false;
}

int findParent (int n)
{
    if ( parent [n] == n ) return n;
    return parent [n] = findParent( parent [n]);
}

int main ()
{
    int m, n;

    while ( scanf ("%d %d", &m, &n) ) {
        if ( m == 0 && n == 0 ) break;

        int totalDist = 0;

        for ( int i = 0; i < n; i++ ) {
            parent [i] = i;
            size [i] = 1;
            scanf ("%d %d %d", &a [i].start, &a [i].end, &a [i].dist);
            totalDist += a [i].dist;
        }

        parent [n] = n;
        size [n] = 1;

        sort (a, a + n, cmp);

        int selected = m - 1;
        int countDist = 0;

        for ( int i = 0; i < n && selected; i++ ) {
            int p = findParent (a [i].start);
            int q = findParent (a [i].end);

            if ( p != q ) {
                if ( size [p] > size [q] ) swap (p, q);
                size [q] += size [p];
                parent [p] = q;
                countDist += a [i].dist;
                selected--;
            }
        }

        printf ("%d\n", totalDist - countDist);
    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

2 thoughts on “UVa : 11631 (Dark roads)

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