689
правок
Изменения
м
→Алгоритм за O(n^3)
Заметим, что искать максимальное паросочетание каждый раз заново необязательно, можно просто постепенно изменять его, получая новые нулевые ребра и строя [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|дополняющие цепи]] на них (примерно так же, как и в [[Алгоритм_Куна_для_поиска_максимального_паросочетания|алгоритме Куна]], но здесь мы фактически строим целое дерево возможных дополняющих цепей).
При их построении нам потребуется сохранять некоторую дополнительную информацию. Для каждого столбца, если в нем есть элемент из текущего паросочетания, будем хранить номер строки этого элемента. Также, при построении дополняющей цепи, будем для каждого элемента паросочетания хранить, на какой элемент добавленный нуль из того же столбца его нужно заменить, если цепь будет проходить через него, а для каждого добавленного нуля - элемент из паросочетания, находящийся в той же строке (если он существует). Эти данные помогут нам восстановить дополняющую цепь.
Будем рассматривать строки матрицы последовательно. Пусть в данный момент мы рассматриваем <tex> i </tex>-ую строку, а в первых <tex> i - 1 </tex> строках максимальное паросочетание уже найдено.
Множество строк <tex> C </tex>, из которых мы будем вычитать минимумы, вначале состоит только из строки <tex> i </tex>, множество <tex> R </tex> пусто. Применим к матрице операцию <tex> C\uparrow\downarrow R </tex>. Если новый ноль нуль с координатами <tex> xy </tex> появился в столбце, не занятом паросочетанием, то удлинняющая цепь найдена, <tex> xy </tex> — ее последнее ребро. Если нет, то существует элемент <tex> x'y </tex> из паросочетания. Тогда добавим строку <tex> x' </tex> и столбец <tex> y </tex> в множества <tex> C </tex> и <tex> R </tex> соответственно и отметим <tex> xy </tex> как замену для <tex> x'y </tex>.
После того, как мы нашли дополняющую цепь, производим серию замен вдоль нее. При этом размер найденного нами паросочетания увеличится.
