Найдите минимальную сумму матрицы (NXN), которая выбирает только одну в каждой строке и столбце

Question

Это еще одна проблема алгоритмов, связанная с динамическим программированием

Вот проблема:

Найдите минимальную сумму данной матрицы такой, что выберите одну в каждой строке и столбце

Например :

3 4 2

8 9 1

7 9 5

Минимальный один: 4 + 1 + 7

Я думаю, что решение - сетевой поток (максимальный поток/мин.

Мое решение: разделить на n list [column], column1, column2 ... столбец n

Затем начальная точка (s) -> column1 -> column2 -> ... -> Column n -> (e) конечная точка и реализация Max Flow/Min Cut

Answer 1

Это Проблема назначения который можно считать особым случаем минимального веса, идеального сопоставления на графиках. Классический способ решения проблемы назначения - использовать Венгерский алгоритм.