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;
}