kuoe0
2/16/2012 - 8:16 AM

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

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

``````/*
* =====================================================================================
*
*       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 (tommy790506@hotmail.com)
*   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;
}

``````