689
правок
Изменения
м
→Алгоритм за O(n^3)
Будем рассматривать строки матрицы последовательно. Пусть в данный момент мы рассматриваем <tex> i </tex>-ую строку, а в первых <tex> i - 1 </tex> строках максимальное паросочетание уже найдено.
Множество строк <tex> C </tex>, из которых мы будем вычитать минимумы, вначале состоит только из строки <tex> i </tex>, множество <tex> R </tex> пусто. Применим к матрице операцию <tex> R\uparrow\downarrow C </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>.
После того, как мы нашли дополняющую цепь, производим серию замен вдоль нее. Цепь состоит из элементов паросочетания и добавленных на текущей итерации нулей, причем для каждого элемента цепи (кроме, разумеется, последнего) известен следующий за ним. После того, как мы удалим из паросочетания все ребра цепи, принадлежащие ему и добавим не принадлежащие, суммарный размер паросочетания увеличится.
