题解

#include<bits/stdc++.h>
using namespace std;

struct node {
	int u , v , w;
    node() {}
	node(int uu , int vv , int ww) {
		u = uu , v = vv , w = ww;
	}
} E[125010];

bool cmp(node a , node b) {
	return a.w < b.w;
}

int fa[510];

void init() {
	for(int i = 0 ; i < 510 ; i++) {
		fa[i] =  i;
	}
}

int get(int x) {
	if(fa[x] == x) return x;
	else {
		int r = get(fa[x]);
		fa[x] = r;
		return r;
	}
}

bool merge(int x , int y) {
	int r1 = get(x) , r2 = get(y);
	if(r1 == r2) {
		return false;
	} else {
		fa[r1] = r2;
		return true;
	}
}
int main() {
	int t;
	cin >> t;
	for(int k = 1 ; k <= t ; k++) {
		int ans = 0;
		init();
		int n , e;
		cin >> n >> e;
		for(int i = 1 ; i <= e ; i++) {
			int u , v , w;
			cin >> u >> v >> w;
			E[i] = node(u , v , w);
		}
		sort(E + 1 , E + 1 + e , cmp);
		for(int i = 1 ; i <= e ; i++) {
			if(merge(E[i].u , E[i].v)) {
				ans += E[i].w;
			}
		}
		cout << ans << endl;
	}
	return 0;
}