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≤C(i,j)≤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≤100).
- Dòng thứ i trong n dòng tiếp theo: dãy m số nguyên dương C1,C2,..,Cm trong đó Cj 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
INPUT:
5 4
31 10 1 1
1 31 12 13
4 10 31 1
6 1 20 19
10 5 10 10
OUTPUT:
2
0
4
1
0
test hơi thiếu
bài này ko có checker hả mn?