Quy hoạch động Bitmask: Bài toán người du lịch TSP
Robot tự hành chịu trách nhiệm bảo trì phần cứng các cụm máy chủ phân tán của AI Empire Academy cần xuất phát từ phòng điều hành trung tâm (đánh số 0), đi qua thăm và kiểm tra tất…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: bitwise operators, dp state compression, std vector.
Nội dung đề bài
Mục tiêu kiến thức
- Nắm vững kỹ thuật biểu diễn tập hợp con bằng số nguyên (Bitmask) và các phép toán bitwise.
- Hiểu cấu trúc trạng thái dp[mask][u] cho bài toán kinh điển Người du lịch (TSP).
- Tối ưu độ phức tạp từ duyệt hoán vị O(N!) xuống O(N2 · 2N) cho N ≤ 16.
Mô tả bài toán
Robot tự hành chịu trách nhiệm bảo trì phần cứng các cụm máy chủ phân tán của AI Empire Academy cần xuất phát từ phòng điều hành trung tâm (đánh số 0), đi qua thăm và kiểm tra tất cả N-1 trạm máy chủ còn lại (đánh số từ 1 đến N-1), mỗi trạm đúng một lần, rồi quay trở về phòng điều hành 0.
Cho ma trận chi phí di chuyển C kích thước N × N, trong đó C[i][j] là chi phí di chuyển một chiều từ trạm i đến trạm j. Chi phí từ một trạm đến chính nó luôn bằng 0 (C[i][i] = 0). Nhiệm vụ của bạn là tìm tổng chi phí di chuyển nhỏ nhất cho toàn bộ hành trình khép kín này.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Một số nguyên N (2 ≤ N ≤ 16) — số lượng trạm.
- N dòng tiếp theo: Mỗi dòng gồm N số nguyên biểu diễn ma trận chi phí C:
- Dòng thứ i chứa C[i][0], C[i][1], …, C[i][N-1] (0 ≤ C[i][j] ≤ 106, C[i][i] = 0).
- Chi phí có thể không đối xứng (C[i][j] có thể khác C[j][i]).
Output
- In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất của chu trình Hamilton xuất phát từ trạm 0, thăm tất cả các trạm và quay về 0.
Ràng buộc
- 2 ≤ N ≤ 16.
- 0 ≤ C[i][j] ≤ 106.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0Output
35Ví dụ 2
Input
2
0 5
7 0Output
12Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.