let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VNEMPIRE - Đế chế

solution.md

Đầu tiên sắp xếp 3 mảng các tọa độ x, y, z tăng dần. Ta thấy cạnh (x[i], x[i+1]) sẽ có độ dài nhỏ hơn cạnh (x[i], x[i+2]). Tương tự với các tọa độ y và z.

Vì vậy, khi làm Kruskal, ban đầu ta chỉ cần xét những cạnh liên tiếp nhau trên 3 mảng đã sắp xếp. Sau khi cạnh (x[i], x[j]) được lấy ra khỏi heap, ta mới thêm cạnh (x[i], x[j+1]) vào heap, tương tự đối với y và z.

Tại mọi thời điểm, số phần tử trong heap là 3N. Độ phức tạp: \(O(N\log N)\).

Trong đoạn code bên dưới, struct edge chứa 2 con trỏ from và to trỏ đến 2 đỉnh của cạnh. Mỗi lần lấy một cạnh ra khỏi heap, ta thêm cạnh mới (from, to + 1) vào heap. Có một phần tử ảo node { -1, 0 } ở cuối mảng để khỏi bị tràn.

main.cpp
Open in Github Download
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct node {
    int name;
    int val;
};

struct edge {
    typedef vector<node>::const_iterator iter;
    iter from, to;
    int val;
    edge(const iter &from, const iter &to): from(from), to(to) {
        val = abs(from->val - to->val);
    }
};

bool operator < (const node &a, const node &b) {
    return a.val < b.val;
}

bool operator > (const edge &a, const edge &b) {
    return a.val > b.val;
}

typedef priority_queue<edge, vector<edge>, greater<edge>> minheap;

void push_edges(minheap& heap, vector<node> &a) {
    sort(a.begin(), a.end());
    a.push_back(node { -1, 0 });
    for (auto iter = a.begin(); iter != a.end() - 2; iter++) {
        heap.push(edge(iter, iter + 1));
    }
}

vector<int> init_set(int n) {
    vector<int> set(n);
    for (int i=0; i<n; i++) set[i] = i;
    return set;
}
int find_root(vector<int> &set, int u) {
    if (set[u] != u) set[u] = find_root(set, set[u]);
    return set[u];
}
bool join(vector<int> &set, int u, int v) {
    u = find_root(set, u);
    v = find_root(set, v);
    if (u == v) return false;
    if (rand() & 1) set[u] = v;
    else set[v] = u;
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    srand(time(NULL));

    int n; cin >> n;
    vector<node> a(n), b(n), c(n);
    for (int i=0; i<n; i++) {
        cin >> a[i].val >> b[i].val >> c[i].val;
        a[i].name = b[i].name = c[i].name = i;
    }

    minheap heap;
    push_edges(heap, a);
    push_edges(heap, b);
    push_edges(heap, c);

    auto set = init_set(n);
    long long res = 0;
    int count = 0;
    while (!heap.empty()) {
        if (count == n - 1) break;
        auto e = heap.top();
        heap.pop();
        if (join(set, e.from->name, e.to->name)) res += e.val, count += 1;
        auto next = e.to + 1;
        if (next->name != -1) heap.push(edge(e.from, next));
    }
    cout << res;
    return 0;
}
Comments