=================================
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 ^^
