QBMST - Cây khung nhỏ nhất ( HEAP )
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
#define fi first
#define se second
int n, m;
vector<i3> g;
int r[10005];
int getr( int u ) {
return u == r[u] ? u : r[u] = getr(r[u]);
}
int main() {
scanf( "%d%d", &n, &m );
for( int i = 0; i < m; ++i ) {
int u, v, l; scanf( "%d%d%d", &u, &v, &l );
g.push_back(i3(l, ii(--u, --v)));
}
sort(g.begin(), g.end());
for( int i = 0; i < n; ++i ) r[i] = i;
int c = 0, res = 0;
for( typeof(g.begin()) it = g.begin(), _e = g.end(); c != n-1 && it != _e; ++it ) {
int u = it->se.fi, v = it->se.se, l = it->fi;
if (getr(u) != getr(v)) {
res += l; ++c;
r[r[u]] = r[v];
}
}
printf( "%d\n", res );
return 0;
}