Как добавляются потенциалы тогда в Hungarian algorithm?

Question

[alex_agaphe]

This is equivalent to subtracting a number from all rows which are not covered and adding the same number to all columns which are covered. These operations do not change optimal assignments. - почему?
потенциа же не измениться

Comments

[Wataru]

Откуда этот текст-то?

Вычитание из всех строк не меняет оптитмальное назначение, потому что вы вычли число из всех строк. любое назначение берет по одному числу из каждой строки, а значит вы изменили стоимость всех назначений на одно и то же число (n*сколько прибавили к каждой строке). А значит оптимальное все еще остается назначением с минимальной стоимостью. Если вы возьмете и все цены в магазине уменьшите на 100рублей, самый дешевый товар остается самым дешевым.

Тоже самое с прибавлением ко всем столбцам.