Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FWATER - Tưới nước đồng cỏ

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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 gửi lên bởi:Jimmy
Ngày:2008-10-22
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO October 2008 - Qualifying Round

hide comments
2017-07-07 05:42:45
lại là thuật toán con trâu điên ;))
2016-02-29 15:38:43
Tham khảo tại: http://phuotvnspoj.blogspot.com/2016/02/fwater-tuoi-nuoc-ong-co-nong-dan-john.html
2015-12-13 17:14:56 Ðặng Phương Tân
AC cả bằng Prim lẫn Kruskal :v
2015-10-08 16:55:23
nh?t coaye..........http://ideone.com/N7DR1q
2015-09-16 18:09:21 Anh Tuấn
mình dùng kruskal sao được có 80 nhỉ
2015-09-13 10:20:11
Tham khảo tại: http://nhatkynghiencuu.blogspot.com/2015/07/tuoi-nuoc-ong-co-ma-fwater-spoj.html
2015-09-11 03:19:32
Tham khảo tại https://traitaodo.wordpress.com/2015/09/11/tuoi-nuoc-dong-co-fwater/
2015-07-16 18:15:55 N�ng D�n John
Nhẹ nhàng với Prim mà, không cần DSU
2015-07-07 04:38:45 quang_proltt
kruskal 1 phat AC nhe :v
2015-05-31 11:30:43 Stupid Dog
sửa đổi thuật toán prim chứ cần gì đỉnh ảo
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.