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

Code QBMST được viết bằng thuật toán Kruskal Pascal Mình đã 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ị: const fi=”; nmax=15500; type data=longint; var f:text; u,v,c:array[1..nmax] of data; root:array[1..nmax] of data; n,m:data; procedure […]

Continue reading


BCDAISY spoj PTIT – Chú bò hư hỏng

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCDAISY/ 1. Đề bài BCDAISY spoj Nông dân John có N (1<=N<=250) con bò đánh số từ 1..N chơi trên bãi cỏ. Để tránh bị lạc mất các con bò, mỗi con bò có thể được nối với một số con bò khác bằng dây thừng. Có tất cả M (1 <= M <= […]

Continue reading


BCBIN spoj PTIT – Các thùng nước

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCBIN/ 1. Đề bài BCBIN spoj Có N thùng nước được đánh số từ 1 đến N, giữa 2 thùng bất kỳ đều có một ống nối có một van có thể khóa hoặc mở. Ở trạng thái ban đầu tất cả các van đều đóng. Bạn được cho một số yêu cầu, trong […]

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