QBMST - Cây khung nhỏ nhất ( HEAP )

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <stdio.h>
#include <iostream>
using namespace std;

int n, m, f[15000];
pair<int, pair<int,int> > a[16600];

int getroot(int i) { return (f[i]<0) ? i : getroot(f[i]); }

void merge(int i, int j) {
	i = getroot(i);
	j = getroot(j);
	if(f[i]>f[j]) swap(i,j);
	f[i] += f[j];
	f[j] = i;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;++i) scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first);
	sort( a, a+m);
	int res = 0;
	memset( f, -1, sizeof(f));
	for(int i=0;i<m;++i) {
		int u = a[i].second.first;
		int v = a[i].second.second;
		if(getroot(u)!=getroot(v)) {
			merge(u,v);
			res += a[i].first;
		}
	}
	printf("%d\n", res);
	return 0;
}

Download