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