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

Download