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
Thảo luận
Không có bình luận