Cây khung nhỏ nhất QBMST spoj: Kruskal, Prim heap

Code tham khảo bài QBMST được viết bằng thuật toán Kruskal (đã bỏ một số phần thừa trong sách TLGK Chuyên tin) Thuật toán kruskal dưới đây được biểu diễn đồ thị bằng danh sách cạnh trong lí thuyết đồ thị:

Code tham khảo bài QBMST được viết bằng Prim Heap

Continue reading


Cấu trúc dữ liệu Disjoint Sets

Nguồn đề bài: http://www.spoj.com/KSTN/problems/DS2509/ 1. Đề bài Cấu trúc dữ liệu Disjoint Sets Disjoint-set hiểu 1 cách đơn giản là 1 cách lưu trữ các tập hợp phần tử của 1 tập lớn cho trước. Các phép toán thường được quan tâm tới trong disjoint-set là: MakeSet(i): tạo ra 1 tập chỉ có i. FindSet(i): tìm tập […]

Continue reading


bài giải NKRACING spoj – Vòng đua F1

Nguồn đề bài http://vn.spoj.com/problems/NKRACING/ 1. Đề bài NKRACING spoj Singapore sẽ tổ chức một cuộc đua xe Công Thức 1 vào năm 2008. Trước khi cuộc đua diễn ra, đã xuất hiện một số cuộc đua về đêm trái luật. Chính quyền muốn thiết kế một hệ thống kiểm soát giao thông để bắt giữ các tay […]

Continue reading