Chuyển tin (Câu 3 đề thi HSG 12 tỉnh Bến Tre năm 2021-2022)
Cần chuyển hết \(n\) gói tin trên một mạng gồm \(m\) kênh truyền. Biết chi phí chuyển \(i\) gói tin trên kênh \(j\) là \(C(i, j)\) \((1 \le C(i,j) \le 10000)\).
Yêu cầu:
- Cho biết một phương án chuyển gói tin với chi phí thấp nhất
Dữ liệu vào:
- Dòng 1: hai số \(n\) và \(m\) \((1 < n, m \le 100)\).
- Dòng thứ \(i\) trong \(n\) dòng tiếp theo: dãy m số nguyên dương \(C_1, C_2,.., C_m\) trong đó \(C_j\) là chi phí chuyển \(i\) gói tin trên kênh \(j\).
Dữ liệu ra:
- Dòng đầu tiên: tổng chi phí thấp nhất theo phương án tìm được.
- Dòng thứ \(j\) trong \(m\) dòng tiếp theo: số lượng gói tin chuyển trên kênh \(j\).
Ví dụ:
| INPUT | OUTPUT |
|---|---|
| 5 4 31 10 1 1 1 31 12 13 4 10 31 1 10 5 10 10 |
2 0 4 1 |
Giải thích:
- Với \(n = 5\) gói tin, \(m = 4\) kênh và chi phí \(C(i, j)\) cho trước, trong đó \(i\) là chỉ số dòng (số gói tin), \(j\) là chỉ số cột (kênh) thì cách chuyển sau đây cho kết quả chi phí thấp nhất là 2.
| Kênh | Số gói tin | Chi phí |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 4 | 1 |
| 3 | 1 | 1 |
| 4 | 0 | 0 |
Comments
bài này ko có checker hả mn?