Изменения

#* В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|нахождение минимального контролирующего множества вершинного покрытия в двудольном графе]]). Теперь применим преобразование <tex> X_c \uparrow\downarrow Y \setminus Y_c </tex>, где <tex> X_c </tex> и <tex> Y_c </tex> — множества вершин минимального контролирующего множества вершинного покрытия из левой и правой долей соответственно. Для этого преобразования <tex> d </tex> будет минимумом по всем ребрам между <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>, то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.

Поиск максимального паросочетания или минимального контролирующего множества вершинного покрытия в двудольном графе совершается за <tex> O(n^3) </tex> операций. При каждом повторении шагов 1-3 в матрице весов появляется новый нуль, который увеличивает размер максимального паросочетания хотя бы на 1, поэтому всего будет совершено <tex> O(n) </tex> итераций внешнего цикла. Поэтому, суммарная асимптотика работы алгоритма — <tex> O(n^4) </tex>.

При их построении нам потребуется сохранять некоторую дополнительную информацию. Для каждого столбца, если в нем есть элемент из текущего паросочетания, будем хранить номер строки этого элемента. Также, при построении дополняющей цепи, будем для каждого элемента паросочетания хранить, на какой добавленный нуль из того же столбца его нужно заменить, если цепь будет проходить через него, а для каждого добавленного нуля {{- --}} элемент из паросочетания, находящийся в той же строке (если он существует). Эти данные помогут нам восстановить дополняющую цепь.