//
you're reading...
Bài tập huấn luyện, Chủ đề xếp lịch công việc

Bài tập huấn luyện: Xây dựng đường

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 9


Đề bài


Vua Peaceful vừa khai hoang một vùng đất để lập ra đất nước Peace, lúc đầu chỉ có N thành phố (được đánh số từ 1 đến N) và không có con đường nào. Vua Peace chọn ra 4 thành phố đặc biệt để làm trung tâm kinh tế và 4 thành phố này phải được liên thông với nhau. Chi phí xây dựng các con đường không phải nhỏ vì thế nhà vua muốn sử dụng chi phí ít nhất để xây dựng các con đường sao cho 4 thành phố đặc biệt đó vẫn liên thông. Bạn được biết chi phí ước tính để xây dựng một số con đường và bạn hãy chọn một số con đường để xây dựng để theo đúng ý nhà vua biết rằng luôn tồn tại ít nhất một phương án xây dựng đường sao cho 4 thành phố đặc biệt liên thông.

Input:    BUILD.INP

  • Dòng đầu tiên ghi số nguyên dương N là số lượng các thành phố.
  • Dòng thứ hai ghi 4 số nguyên là số hiệu của 4 thành phố đặc biệt.
  • Trong một số dòng tiếp theo, mỗi dòng ghi 3 số nguyên u, v và c với ý nghĩa muốn xây dựng một con đường hai chiều nối trực tiếp giữa 2 thành phố u và v thì chi phí là c.

Output: BUILD.OUT

  • Dòng đầu tiên tổng chi phí nhỏ nhất để xây dựng hệ thống đường.
  • Trong một số dòng tiếp theo, mỗi dòng ghi 2 số nguyên u và v với ý nghĩa cần xây dựng con đường 2 chiều nối giữa 2 thành phố u và v.

Giới hạn:

  • 1 ≤ N ≤ 100
  • 1 ≤ c ≤ 5000
  • Thời gian: 0.5 s/test
  • Bộ nhớ: 1 MB

Ví dụ:

BUILD.INP BUILD.OUT
5

2 3 4 1

1 2 10

1 5 1

5 2 1

1 4 1

4 3 3

3 2 2

5

1 5

5 2

3 2

4 1

 


Hướng dẫn


[]


Chương trình


[]

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ả

Danh mục

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Palouse Falls at Sunrise (Palouse, WA)

Dartford Warbler

Herbal face

More Photos

Thống kê

  • 137,116 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: