Chuyển tin (Câu 3 đề thi HSG 12 tỉnh Bến Tre năm 2021-2022)


Submit solution

Points: 50
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

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


  • 0
    letrongdoan  commented on Aug. 8, 2024, 6:15 a.m. edit 2

    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


  • 0
    Cody  commented on Aug. 2, 2024, 8:48 p.m.

    test hơi thiếu


  • 0
    FREEO7  commented on Nov. 1, 2023, 12:31 a.m.

    bài này ko có checker hả mn?