Венгерский алгоритм для неквадратной матрицы

Question

Я пытаюсь реализовать венгерский алгоритм. Все хорошо, за исключением случаев, когда матрица не квадратная. Все методы, которые я искал, говорят, что я должен сделать это квадратным путем добавления фиктивных строк / столбцов и заполнения фиктивной строки / столбца максимальным числом в матрице. Мой вопрос: не повлияет ли это на конечный результат? Разве фиктивная строка / столбец не должна быть заполнена как минимум max+1?

Answer 1

Фиктивные значения должны быть равны нулю. Дело в том, что не имеет значения, какой из них вы выберете, вы в конце концов проигнорируете этот выбор, потому что его не было в исходных данных. Устанавливая их на ноль (в начале), ваш алгоритм не должен будет работать так усердно, чтобы найти значение, которое вы не собираетесь использовать.

Answer 2

Основная идея венгерского алгоритма основана на том факте, что "оптимальное назначение заданий остается неизменным, если число добавляется / вычитается из всех записей любой строки или столбца матрицы". Следовательно, не имеет значения, используете ли вы фиктивное значение в качестве "max или max+1 или 0". Это может быть установлено как любое число, и лучше это 0 (как сказал Yay295, алгоритм хотел бы работать меньше, если записи уже 0)