Задача о назначениях с недопустимыми назначениями

Итак, имеется задача о назначениях. Дана матрица m x n , в ней есть положительные числа и "NaN".

Альтернативная форма - дан взвешенный двудольный (но не обязательно полный двудольный) граф.

Надо так выбрать числа в матрице, чтобы их было максимальное количество, в каждой строке и столбце стояло не больше одного, и сумма была минимальна. NaN учитываться не должны, такое назначение невозможно.

Альтернативно: наибольшее паросочетание с минимальной суммой чисел на рёбрах, но граф не полный, ребер, для которых в матрице NaN, нет.

Решение: везде вместо NaN записываем "достаточно много", запускаем например венгерский метод и получаем что хотели. Но! Только в том случае, если в матрице вообще возможно выбрать паросочетание размера min (m,n). В противном случае (например, весь какой-то столбец забит NaN) большие числа лезут в решение.

Внимание, вопрос! Правильно ли я понимаю, что если потом просто удалить из такого ответа все назначения ценой в "очень много", то оставшиеся как раз и будут составлять наше оптимальное для исходной задачи с недопустимыми?