View Code of Problem 3284

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 50010;
int N,M,R;
int n;
struct edge{ 
	int a,b;
	int v; 
}s[maxn]; 
int pre[maxn];
bool cmp(edge a,edge b){return a.v < b.v;} 
int Find(int a){ 
	int root = a; 
	int tmp; 
	while(root != pre[root])root = pre[root]; 
	while(a != root){ 
		tmp = a; 
		a = pre[a]; 
		pre[tmp] = root; 
	} 
	return root; 
} 
void combine(int a,int b){ 
	int x = Find(a); 
	int y = Find(b); 
	if(x > y) 
		swap(x,y); 
	pre[y] = x; 
}
void kruskal(){ 
	int ans = 0;
	sort(s, s + R, cmp);
	for(int i=0;i<=N+M;i++)
	{
		pre[i]=i;
	}	
	for(int i=0;i<R;i++){ 
		if(Find(s[i].a)!=Find(s[i].b)){ 
 			combine(s[i].a,s[i].b); 
 			ans += s[i].v; 
 		} 
 	} 
 	printf("%d\n", 10000 * (N + M) + ans);
}
int main(){
	scanf("%d", &n);
	while (n--) {  
		scanf("%d %d %d", &N, &M, &R);
		int nx, ny, cc;
		for (int i = 0; i < R; ++i) {
			scanf("%d %d %d", &nx, &ny, &cc);
			s[i].a = nx;
			s[i].b = N + ny;
			s[i].v = -cc;  
		}
		
		kruskal();
	}
	
	return 0;
}