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