[POJ] 3723 - Conscription - http://kuoe0.ch/1515/poj-3723-conscription/

3723 - Conscription.cpp

/*
 * =====================================================================================
 *
 *       Filename:  3723 - Conscription.cpp
 *
 *    Description:  http://poj.org/problem?id=3723
 *
 *
 *        Version:  1.0
 *        Created:  2012/02/16 14時59分31秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  KuoE0 ([email protected])
 *   Organization:  NCKU WMMKS Lab, Taiwan
 *
 * =====================================================================================
 */
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 10010


vector< int > set, rank;

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

void union_set( int a, int b ) {
	if ( rank[ a ] > rank[ b ] )
		set[ b ] = a;
	else {
		set[ a ] = b;
		if ( rank[ a ] == rank[ b ] )
			++rank[ b ];
	}
}

int main() {

	int t, N, M, R;
	scanf( "%d", &t );
	while ( t-- ) {

		vector< pair< int, pair< int, int > > > rel;
		scanf( "%d %d %d", &N, &M, &R );

		set = rank = vector< int >( N + M, 0 );
		for ( int i = 0; i < N + M; ++i )
			set[ i ] = i;

		int x, y, d;
		for ( int i = 0; i < R; ++i ) {
			scanf( "%d %d %d", &x, &y, &d );
			rel.push_back( pair< int, pair< int, int > >( d, pair< int, int >( x, N + y ) ) );
		}

		long long int cnt = 0;
		sort( rel.begin(), rel.end(), greater< pair< int, pair< int, int > > >() );

		for ( int i = 0; i < rel.size(); ++i ) {
			x = rel[ i ].second.first, y = rel[ i ].second.second;
			if ( find_set( x ) != find_set( y ) ) {
				cnt += rel[ i ].first;
				union_set( find_set( x ), find_set( y ) );
			}
		}
		printf( "%lld\n", 10000 * ( long long )( N + M ) - cnt );

	}
	return 0;
}