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

Bài tập huấn luyện: Gặp gỡ

 

Hiện nay IOICamp có rất nhiều thành viên từ N thành phố. Các thành phố đánh số từ 1 đến N. Tại thành phố thứ i (1 £ i £ N) có Ti thành viên và ta gọi tổng số thành viên ở N thành phố là S. Có tất cả M đoạn đường hai chiều nối các thành phố sao cho giữa hai thành phố có không quá một đoạn đường nối trực tiếp và hệ thống đường luôn liên thông. Đối với mỗi đoạn đường, ta biết được thời gian để đi trên các đoạn đường đó.

Do số thành viên rất đông nên khó có thể tập trung tất cả ở một thành phố, vì vậy Admin dự định lập một kế hoạch gặp gỡ giao lưu tại K thành phố sao cho:

  • K thành phố được chọn là khác nhau.
  • Tổng số các thành viên đến mỗi thành phố giao lưu đều bằng S/K (K luôn đảm bảo là ước của S).
  • Tổng thời gian đi đến nơi tập trung của tất cả các thành viên theo con đường nhanh nhất là ít nhất.

Bạn hãy giúp Admin lập một kế hoạch hoàn hảo nhất cho cuộc giao lưu bằng cách chọn ra K thành phố và chỉ ra một phương án để các thành viên có thể di chuyển đến K thành phố này.

Ngay cả nếu kế hoạch của bạn không phải là phương án tối ưu thì bạn cũng nên đưa cho Admin một lời giải tốt nhất của mình.

Input: MEETING.INP

  • Dòng đầu tiên ghi 3 số nguyên dương N, M và K lần lượt là số thành phố, số đoạn đường và số thành phố cần chọn.
  • Dòng thứ hai ghi N số tự nhiên T1, T2, .., TN là số thành viên ở các thành phố.
  • Trong M dòng cuối cùng, mỗi dòng ghi 3 số nguyên dương X, Y, Z với ý nghĩa có đoạn đường hai chiều nối trực tiếp 2 thành phố X, Y và thời gian để đi đoạn đường này là Z.

Output:            MEETING.OUT

  • Dòng đầu tiên K số nguyên dương X1, X2, .., XK là tên K thành phố được chọn.
  • Dòng thứ i trong N dòng tiếp theo ghi K số tự nhiên Di1, Di2, .., DiK với ý nghĩa sẽ có Dij thành viên từ thành phố i đến thành phố Xj (1 ≤ i ≤ N, 1 ≤ j ≤ K).

Giới hạn:

  • 1 ≤ N ≤ 10000 ; 1 ≤ M ≤ 30000 ; 1 ≤ K ≤ 100
  • 0 ≤ Ti ≤ 1000 (với mọi 1 ≤ i ≤ N)
  • 0 < Z ≤ 200 với mọi đoạn đường
  • Thời gian: 2 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

MEETING.INP MEETING.OUT
4 4 2

2 40 100 10

1 2 2

1 4 2

4 3 1

2 3 1

2 3

2 0

40 0

34 66

0 10

Ghi chú: Với phương án trên thì tổng thời gian di chuyển của các thành viên là 48

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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

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

NCT Computer

Flickr Photos

Thống kê

  • 209,568 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: