Mã bài:
dtqg_cvrpopt
Điểm:
3,7 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Một đội xe tải gồm ~K~ chiếc có cùng tải trọng ~Q~ cần được lên lịch để vận chuyển các thùng Pepsi từ một kho trung tâm ~0~ đến các khách hàng ~1, 2, ..., n~. Mỗi khách hàng ~i~ yêu cầu ~d[i]~ thùng hàng. Khoảng cách từ địa điểm ~i~ đến địa điểm ~j~ là ~c[i, j],~ ~0 ≤ i, j ≤ n~. Một phương án vận chuyển là một tập hợp các lộ trình: mỗi xe tải được gán với một lộ trình, bắt đầu từ kho, ghé thăm một số khách hàng và quay trở lại kho để giao các thùng hàng Pepsi theo yêu cầu sao cho:
- Mỗi khách hàng chỉ được ghé thăm đúng một lần bởi một lộ trình
- Tổng số thùng hàng yêu cầu của khách hàng trong mỗi xe tải không vượt quá khả năng chứa của nó
- Mỗi xe tải phải ghé thăm ít nhất một khách hàng
Mục tiêu: Tìm phương án sao cho tổng khoảng cách di chuyển nhỏ nhất
Lưu ý: thứ tự của các khách hàng trong một lộ trình là quan trọng, ví dụ, lộ trình ~0 \to 1 \to 2 \to 3 \to 0~ và ~0 \to 3 \to 2 \to 1 \to 0~ là khác nhau.
Dữ liệu vào
- Dòng ~1~: ~n, K, Q~ ~(2 ≤ n ≤ 10, 1 ≤ K ≤ 5, 1 ≤ Q ≤ 20)~
- Dòng ~2~: ~d[1], ..., d[n]~ ~(1 ≤ d[i] ≤ min(Q, 10))~
- Dòng ~i + 3~: hàng thứ ~i~ của ma trận khoảng cách ~c(i = 0, ..., n)~ ~(0 \leq c[i, j] \leq 10^9)~
Dữ liệu ra
Tổng khoảng cách di chuyển nhỏ nhất.
Sample Input
4 2 15
7 7 11 2
0 12 12 11 14
14 0 11 14 14
14 10 0 11 12
10 14 12 0 13
10 13 14 11 0
Sample Output
70
Bình luận