//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Cấp nước

 

Để đảm bảo cung cấp nước sạch cho N địa điểm dân cư được đánh số từ 1 đến N, người ta đã xây dựng nhà máy nước tại địa điểm dân cư 1 và lập dự án xây dựng mạng đường ống bao gồm M tuyến đường ống, mỗi tuyến đường ống nối hai trong số các địa điểm dân cư còn lại. Rất tiếc do vốn đầu tư hạn hẹp nên không thể thực hiện ngay việc xây dựng toàn bộ các tuyến đường ống. Vì vậy, trong giai đoạn đầu của việc thực hiện dự án, người ta cần phải tìm cách xây dựng trước một só tuyến đường ống trong dự án đảm bảo việc truyền tải nước theo các tuyến đường ống này tới K địa điểm ưu tiên. Cho biết chi phí xây dựng của mỗi tuyến đường ống của dự án, hãy xác định các tuyến đường ống cần xây dựng trước để đáp ứng nhu cầu đặt ra với tổng chi phí xây dựng là nhỏ nhất.

Input: WATERNET.INP

  • Dòng đầu tiên chứa 3 số nguyên dương được ghi cách nhau bởi dấu cách N, M, K.
  • Dòng thứ hai chứa K số nguyên dương là các chỉ số của các địa điểm ưu tiên.
  • Dòng thứ i trong M dòng tiếp theo chứa 3 số nguyên dương được ghi cách nhau bởi dấu cách Si, Ti, Ci trong đó Si và Ti là điểm đầu và điểm cuối của tuyến đường ống, còn Ci là chi phí để xây dựng tuyến đường ống này.

Output: WATERNET.OUT

  • Dòng đầu tiên chứa tổng chi phí của các tuyến đường ống được lựa chọn để xây dựng trước.
  • Dòng thứ hai chứa số lượng tuyến đường ống được lựa chọn xây dựng trước P.
  • Mỗi dòng trong số P dòng tiếp theo chưa hai đầu mút của một tuyến đường ống được lựa chọn xây dựng trước.

Giới hạn:

  • K < N ≤ 1000
  • M ≤ 10000
  • Thời gian: 2 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

WATERNET.INP WATERNET.OUT
5 8 1

2

1 4 4

5 1 15

1 3 10

3 5 8

2 3 12

2 5 20

4 5 21

4 2 13

17

2

4 1

4 2

 

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Pine Martens

King

Alfred Nicholas Memorial Gardens 2017-03-18 (5D_32A6187)

More Photos

Thống kê

  • 115,063 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: