VNEMPIRE - Đế chế - Solution for SPOJ

Problem

https://vn.spoj.com/problems/VNEMPIRE

https://oj.vnoi.info/problem/VNEMPIRE

Một đế chế đang xây dựng mạng lưới cho các hành tinh trong nó. Đế chế gồm có N hành tinh được biểu diễn như các điểm trong không gian 3 chiều. Chi phí phải chi cho việc nối giữa hành tinh A và hành tinh B là

min{ |xA - xB|, |yA - yB|, |zA - zB| }

với (xA, yA, zA), (xB, yB, zB) là tọa độ của hành tinh A, B trong không gian 3 chiều.

Đế chế dự tính sẽ xây dựng N – 1 cầu nối như vậy để các hành tinh liên thông với nhau và chi phí để trả sao cho phải nhỏ nhất có thể.

Dữ liệu

Dòng đầu là số hành tinh N (N <= 100,000).
N dòng sau mỗi dòng là tọa độ của một hành tinh.

Kết quả

Ghi trên một dòng duy nhất chi phí nhỏ nhất có thể.

Ví dụ

Input
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

Output
4 

Tutorial

Hơi hướng của một bài Minimum Spanning Tree - Cây khung nhỏ nhất.

Rõ ràng cần tìm ra cây khung nhỏ nhất trong đồ thị, tuy nhiên số cạnh là quá lớn trong trường hợp này, N^3 cạnh, do là đồ thị đầy đủ.

Tuy nhiên dựa trên yếu tố min{ |xA - xB|, |yA - yB|, |zA - zB| }, ta có thể giới hạn số cạnh của bài toán lại còn 3N cạnh, tức chỉ chọn ra 3N cạnh nhỏ nhất được chọn theo 3 trục của hệ tọa độ. Cụ thể trên mỗi trục tọa độ, ta chỉ chọn các cạnh nối các điểm liền kề nhau (theo trục đang xét), vì những cạnh còn lại sẽ không tạo được cây khung tối ưu.

Lấy ví dụ trong hệ tọa độ 2 chiều như hình phía dưới.

Xét trên trục X, 3 điểm A, B, C lần lượt theo thứ tự từ trái sang phải. Nhận thấy cạnh AC là cạnh không được chọn trong cây khung sau cùng.

Do đó bài toán đưa về giải quyết cây khung nhỏ nhất trên tập 3N cạnh, giải quyết bằng DSU (hay Kruskal)

Submission

VNEMPIRE.cpp

Tutorial SPOJ

VNEMPIRE - Đế chế