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 […]
Cây khung
UPGRANET spoj – VOI 2011 Nâng cấp mạng
Nguồn đề bài: http://vn.spoj.com/problems/UPGRANET/ 1. Đề bài UPGRANET spoj Một hệ thống gồm n máy tính đánh số từ 1 đến n được kết nối thành một mạng bởi m đoạn cáp mạng đánh số từ 1 đến m. Đoạn cáp mạng thứ i có thông lượng wi kết nối hai máy ui, vi cho phép […]
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 <= […]
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 […]
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 […]
FWATER spoj – Tưới nước đồng cỏ
Nguồn đề bài: http://vn.spoj.com/problems/FWATER/ 1. Đề bài FWATER spoj Nông dân John quyết định mang nước tới cho N (1 <= N <= 300) đồng cỏ của mình, để thuận tiện ta đánh số các đồng cỏ từ 1 đến N. Để tưới nước cho 1 đồng cỏ John có thể chọn 2 cách, 1 là […]
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 […]
