Một lãnh thổ có N thành phố (3≤ N ≤50) được đánh số từ 1 đến N. Trong một cuộc trưng cầu dân ý, người ta cần đặt một số hòm phiếu tại một trung tâm thành phố nơi mọi người từ n thành phố đi bỏ phiếu. Tuy nhiên, để số người đi bỏ phiếu là nhiều nhất có thể được, người ta muốn đặt các hòm phiếu sao cho quãng đường người đi phải xa nhất là ngắn nhất có thể được.
Yêu cầu: Hãy tìm cách đặt các hòm phiếu sao cho đạt được mục đích đó.
Dữ liệu vào: Cho bởi file HOMPHIEU.INP bao gồm:
- Dòng đầu là 2 số nguyên dương N, k(là số thành phố và số hòm phiếu cần đặt)
- N dòng tiếp theo là ma trận khoảng cách giữa các thành phố.
Dữ liệu ra: ghi ra file HOMPHIEU.OUT bao gồm:
- Dòng đầu ghi quãng đường mà người phải đi xa nhất.
- Dòng tiếp theo ghi lần lượt các thành phố cần đặt hòm phiếu.
Ví dụ
Yêu cầu: Hãy tìm cách đặt các hòm phiếu sao cho đạt được mục đích đó.
Dữ liệu vào: Cho bởi file HOMPHIEU.INP bao gồm:
- Dòng đầu là 2 số nguyên dương N, k(là số thành phố và số hòm phiếu cần đặt)
- N dòng tiếp theo là ma trận khoảng cách giữa các thành phố.
Dữ liệu ra: ghi ra file HOMPHIEU.OUT bao gồm:
- Dòng đầu ghi quãng đường mà người phải đi xa nhất.
- Dòng tiếp theo ghi lần lượt các thành phố cần đặt hòm phiếu.
Ví dụ
| HOMPHIEU.INP | HOMPHIEU.OUT |
| 4 2 0 8 0 9 8 0 2 0 0 2 0 2 9 0 2 0 | 2 1 3 |
