Bài Toán Phân Công

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ công nhân và $n$ công việc. Mỗi công nhân phải thực hiện đúng một công việc, và mỗi công việc phải được giao cho đúng một công nhân.

Chi phí để công nhân $i$ thực hiện công việc $j$ là $c_{i j}$ . Tìm cách phân công sao cho tổng chi phí nhỏ nhất, và in ra cách phân công đó.

Dòng đầu tiên chứa số nguyên $n$ — số công nhân và số công việc.

$n$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên $c_{i 1}, c_{i 2}, \dots, c_{i n}$ — chi phí cho công nhân $i$ thực hiện từng công việc.

Dòng đầu tiên in tổng chi phí nhỏ nhất.

$n$ dòng tiếp theo, mỗi dòng in hai số nguyên $a$ và $b$ — công nhân $a$ được giao công việc $b$ .

Input	Output	Giải thích
4 17 8 16 9 7 15 12 19 6 9 10 11 14 7 13 10	33 1 4 2 1 3 3 4 2	Công nhân 1→công việc 4 (9), công nhân 2→công việc 1 (7), công nhân 3→công việc 3 (10), công nhân 4→công việc 2 (7). Tổng: 33.

Bình luận

Không có bình luận tại thời điểm này.