Məsələlər
Задача о назначениях
Задача о назначениях
Одной из классических задач комбинаторной оптимизации является так называемая "\textit{задача о назначениях}". Формулируется она следующим образом.
Есть $n$ работников, пронумерованных числами от $1$ до $n$, и $n$ работ, также пронумерованных числами от $1$ до $n$. Если $i$-ый работник выполняет $j$-ую работу, то ему выплачивается зарплата в размере $c_{ij}$ денежных единиц. Необходимо найти такое назначение работников на работы (каждый работник выполняет ровно одну работу, каждая работа выполняется ровно одним работником), что суммарная зарплата работников минимальна (соответствующая сумма называется \textit{стоимостью назначения}).
Напишите программу, решающую задачу о назначениях.
\InputFile
Первая строка содержит целое число $n\:(1 \le n \le 10)$.
Каждая из следующих $n$ строк содержит $n$ чисел. При этом $j$-ое число $(i + 1)$-ой строки равно $c_{ij} (1 \le c_{ij} \le 1000)$.
\OutputFile
Выведите минимальную возможную стоимость назначения.
Giriş verilənləri #2
2 1 2 3 4
Çıxış verilənləri #2
5
Giriş verilənləri #1
3 5 2 3 4 2 1 3 7 6
Çıxış verilənləri #1
6