//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Xây cầu vượt biển

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


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


Đề bài


Đất nước Delta là quốc đảo lớn trên thế giới. Đất nước gồm N đảo được đánh số từ 1 đến N. Việc đi lại giữa các đảo là rất khó khăn. Vì kinh tế còn rất kém phát triển, nhà nước phải khó khăn lắm mới mở được N – 1 tuyến phà biển để người dân người dân có thể đi lại được giữa hai đảo bất kì. Cách đây không lâu, đất nước mới nhận được sự đầu tư lớn của các nước. Nhà vua quyết định xây mới K cây cầu vượt biển để thay thế cho K tuyến phà. Các cây cầu mới được xây dựng sẽ nối liền hai đảo mà trước đây có tuyến phà nối trực tiếp. Nhà vua muốn chọn K tuyến phà để thay thế bằng cầu sao cho tổng thời gian đi lại giữa mọi cặp đảo khác nhau là nhỏ nhất.

Bạn hãy chọn ra K trong số N – 1 tuyến phà để thay thế bằng cầu thoả mãn yêu cầu của nhà vua. Nếu có nhiều phương án tương đương, bạn chỉ cần đưa ra một phương án.

Input     BRIDGES.INP

  • Dòng thứ nhất ghi 4 số nguyên N, K, VP, VC trong đó VP là vận tốc nếu đi bằng phà và VC là vận tốc nếu đi bằng cầu. VP và VC có đơn vị là m/s.
  • N – 1 dòng tiếp theo, dòng thứ I ghi thông tin về tuyến phà thứ I gồm 3 số U V L có nghĩa tuyến phà thứ I nối hai đảo U, V và khoảng cách giữa U và V là L mét.

Output  BRIDGES.OUT

  • In ra K số là số hiệu của tuyến phà cần được thay thế bằng cầu.

Ví dụ:

BRIDGES.INP BRIDGES.OUT
6 2 1 2

1 2 5

3 2 6

1 4 4

4 6 4

4 5 5

1

3

dt07

Các giới hạn:

  • 1 ≤ K < N ≤ 10 000
  • 1 ≤ VP, VC ≤ 100 000
  • 1 ≤ LUV ≤ 106

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ả

Chuyên 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

lost

Lookkk deeeply into my eyes....

Cimitero San Michele

More Photos

Thống kê

  • 115,518 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: