ĐỘNG VIÊN ĐÀN BÒ - mã: CHEER - SPOJ


Link: http://vn.spoj.com/problems/CHEER/
=================================


Bác John dạo này lười đến nỗi không muốn bảo trì các con đường dẫn bác đến thăm N (5 <= N <= 10,000) cánh đồng (đánh số từ 1 đến N) nữa. Mỗi cánh đồng là nơi ở của một cô bò. Bác John có kế hoạch loại bỏ nhiều nhất P (N-1 <= P <= 100,000) con đường sao cho các cánh đồng vẫn liên thông.
Ban phải xác định N-1 con đường cần giữ lại.
Đường nối hai chiều j nối giữa cánh đồng Sj và Ej (1 <= Sj <= N; 1 <= Ej <= N; Sj # Ej) và cần Lj (0 <= Lj <= 1000) thời gian để di chuyển. Không có hai cánh đồng nào được nối trực tiếp bởi nhiều hơn một con đường.
Đàn bò buồn vì hệ thống giao thông của chúng sắp bị rút gọn. Bạn phải thăm mỗi cô bò ít nhất một lần trong ngày để động viên. Mỗi lần thăm cánh đồng i (dù chỉ đi ngang qua), bạn phải trò chuyện với cô bò trong thời gian Ci (1 <= Ci <= 1000).
Bạn sẽ nghỉ lại đêm trên cùng một cánh đồng (bạn sẽ được chọn) cho đến khi đàn bò đều đã hết bị suy sụp. Bạn sẽ trò chuyện với cô bò trong cánh đồng mà bạn nghỉ lại ít nhất 2 lần vào buổi sáng thức dậy và vào buổi tối khi trở về nghỉ.
Giả dụ bác John theo lời khuyên của bạn giữ lại một số con đường và bạn sẽ chọn cánh đồng tối ưu nhất để nghỉ lại, hãy xác định thời gian nhỏ nhất bạn cần để thăm tất cả đàn bò ít nhất một lần trong ngày.
Dữ liệu
* Dòng 1: Hai số nguyên N và P cách nhau bởi khoảng trắng
* Dòng 2..N+1: Dòng i+1 chứa một số nguyên duy nhất Ci
* Dòng N+2..N+P+1: Dòng N+j+1 chứa ba số nguyên phân biệt: Sj, Ej và Lj
Kết quả
* Dòng 1: Một số nguyên duy nhất, tổng thời gian cần để thăm tất cả đàn bò (bao gồm hai lần thăm cô bò ở nơi mà bạn nghỉ).
Ví dụ
Dữ liệu:
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

Kết quả:

176

===========================================
thuật: cây khung - thuật Kruskal
- thay đổi trọng số cạnh (u,v) = 2*w + C[u] + C[v] (coi như ta có hai lần đi qua cạnh u và v => đi qua u và đi qua v)
- sử dụng Kruskal tìm cây khung nhỏ nhất
===========================================

Code: CHEER.PAS
























 Continue Reading

ĐẾ CHẾ - mã: VNEMPIRE - SPOJ


Link: http://vn.spoj.com/problems/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 < 100001).
  • N dòng sau mỗi dòng là tọa độ của một hành tinh.
Kết qủa
Ghi trên một dòng duy nhất chi phí nhỏ nhất có thể.
Ví dụ

Dữ liệu
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

Kết qủa
4

Solution: VNEMPIRE
Code: VNEMPIRE.PAS











 Continue Reading

TƯỚI NƯỚC ĐỒNG CỎ - mã: FWATER - SPOJ


Link: http://vn.spoj.com/problems/FWATER/
=================================
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à đào ở đồng cỏ đó 1 cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ trước đó đã có nước tới.
Để đào một cái giếng ở đồng cỏ i cần 1 số tiền là W_i (1 <= W_i <= 100,000). Lắp ống dẫn nước nối 2 đồng cỏ i và j cần 1 số tiền là P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).
Tính xem nông dân John phải chi ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.
DỮ LIỆU
  • Dòng 1: Một số nguyên duy nhất: N
  • Các dòng 2..N + 1: Dòng i+1 chứa 1 số nguyên duy nhất: W_i
  • Các dòng N+2..2N+1: Dòng N+1+i chứa N số nguyên cách nhau bởi dấu cách; số thứ j là P_ij
KẾT QUẢ
  • Dòng 1: Một số nguyên duy nhất là chi phí tối thiểu để cung cấp nước cho tất cả các đồng cỏ.
VÍ DỤ
Dữ liệu
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0


Kết quả
9
GIẢI THÍCH
Có 4 đồng cỏ. Mất 5 tiền để đào 1 cái giếng ở đồng cỏ 1, 4 tiền để đào ở đồng cỏ 2, 3 và 3 tiền để đào ở đồng cỏ 4. Các ống dẫn nước tốn 2, 3, và 4 tiền tùy thuộc vào nó nối đồng cỏ nào với nhau.
Nông dân John có thể đào 1 cái giếng ở đồng cỏ thứ 4 và lắp ống dẫn nối đồng cỏ 1 với tất cả 3 đồng cỏ còn lại, chi phí tổng cộng là 3 + 2 + 2 + 2 = 9.

 ==========================================

Cách làm: 
+ Đối với mảng P, ta tạo thêm dòng n+1 và cột n+1 chứa chi phí của các giếng nước:

 procedure enter();
var i,j,u,v: longint;
begin
    readln(N);
    for i:=1 to n do begin readln(u); P[n+1,i]:=u; P[i,n+1]:=u end;
    for i:=1 to n do
    for j:=1 to n do read(P[i,j]);
    inc(n);
end;

 + Áp dụng thuật toán Prim,  ok
Chúc các bác AC ^^





Continue Reading

XÂY DỰNG THÀNH PHỐ - mã: NKCITY - SPOJ


Link: http://vn.spoj.com/problems/NKCITY/
======================================
Nước Anpha đang lập kế hoạch xây dựng một thành phố mới và hiện đại. Theo kế hoạch, thành phố sẽ có N vị trí quan trọng, được gọi là N trọng điểm và các trọng điểm này được đánh số từ 1 tới N. Bộ giao thông đã lập ra một danh sách M tuyến đường hai chiều có thể xây dựng được giữa hai trọng điểm nào đó. Mỗi tuyến đường có một thời gian hoàn thành khác nhau.
Các tuyến đường phải được xây dựng sao cho N trọng điểm liên thông với nhau. Nói cách khác, giữa hai trọng điểm bất kỳ cần phải di chuyển được đến nhau qua một số tuyến đường. Bộ giao thông sẽ chọn ra một số tuyến đường từ trong danh sách ban đầu để đưa vào xây dựng sao cho điều kiện này được thỏa mãn.
Do nhận được đầu tư rất lớn từ chính phủ, bộ giao thông sẽ thuê hẳn một đội thi công riêng cho mỗi tuyến đường cần xây dựng. Do đó, thời gian để hoàn thành toàn bộ các tuyến đường cần xây dựng sẽ bằng thời gian lâu nhất hoàn thành một tuyến đường nào đó.
Yêu cầu: Giúp bộ giao thông tính thời gian hoàn thành các tuyến đường sớm nhất thỏa mãn yêu cầu đã nêu.
Dữ liệu
Dòng chứa số N và M (1 ≤ N ≤ 1000; 1 ≤ M ≤ 10000).
M tiếp theo, mỗi dòng chứa ba số nguyên u, v và t cho biết có thể xây dựng tuyến đường nối giữa trọng điểm u và trọng điểm v trong thời gian t. Không có hai tuyến đường nào nối cùng một cặp trọng điểm.
Kết quả
Một số nguyên duy nhất là thời gian sớm nhất hoàn thành các tuyến đường thỏa mãn yêu cầu đã nêu.
Ví dụ
Dữ liệu
5 7
1 2 2
1 5 1
2 5 1
1 4 3
1 3 2
5 3 2
3 4 4  

Kết quả

3

=========================
Thuật Toán Prim....^^
 Continue Reading
Subscribe to: Posts (Atom)
 
CẢM ƠN CÁC BẠN ĐÃ XEM !!! ×