Kỳ thi chọn học sinh giỏi cấp tỉnh Lớp 12 THPT môn Tin học (Vòng 2) - Sở GD&ĐT Đồng Tháp (Có hướng dẫn chấm)

(Bản scan)

Bài 3: (7 điểm) PHÂN CÔNG
Một công ty có tên ABC muốn phân công K công việc cho K công nhân. Mỗi công
nhân thứ ¡ có khả năng thực hiện công việc thứ j trong thời gian là † (0trả theo đơn vị thời gian cho mỗi công nhân là bằng nhau, cho nên công ty muốn tìm cách phân
công mỗi người đều có một công việc để làm và mong muốn tổng thời gian thực hiện K công .
việc là nhỏ nhất để tiết kiệm cho công ty.
Yêu cầu: Cho bảng khả năng thực hiện từng công việc của mỗi công nhân. Hãy lập lịch ˆ
phân công sao cho tổng thời gian thực thí K công việc là ít nhất.
Dữ liệu vào: Cho từ tệp văn bản PHANCONG.INP gồm: `
Dòng thứ nhất ghi số nguyên đương K (0Các dòng tiếp theo chứa giá trị tị. 
Kết quả: Ghi ra tệp văn PHANCONG.OUT có duy nhất một dòng chứa số nguyên dương
là tông thời gian của lịch phân công tìm được.