QBMST - Cây khung nhỏ nhất ( HEAP )
Tác giả: ladpro98
Ngôn ngữ: C++
//http://vn.spoj.com/problems/QBMST/
#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 10050;
const int M = 15050;
using namespace std;
int n, m;
int lab[N];
iii e[M];
int root(int u) {
if (lab[u] <= 0) return u;
return lab[u] = root(lab[u]);
}
void unite(int u, int v) {
if (lab[u] < lab[v]) lab[v] = u;
else {
if (lab[u] == lab[v]) lab[v]--;
lab[u] = v;
}
}
int main()
{
scanf("%d %d", &n, &m);
int i, x, y, cnt = 0, res = 0;
for(i = 1; i <= m; i++)
scanf("%d %d %d", &e[i].Y.X, &e[i].Y.Y, &e[i].X);
sort(e + 1, e + 1 + m);
for(i = 1; i <= m; i++) {
x = root(e[i].Y.X); y = root(e[i].Y.Y);
if (x != y) {
unite(x, y);
res += e[i].X;
cnt++;
}
if (cnt == n - 1) break;
}
printf("%d", res);
return 0;
}