39
правок
Изменения
м
→Реализация
<tex> \mathtt{a[1 \dots n][1 \dots m]} </tex> {{---}} прямоугольная входная матрица, где <tex> \mathtt{n \leqslant m} </tex>. Матрица хранится в 1-индексации.
<tex> \mathtt{u[0 \dots n], v[0 \dots n]} </tex> {{---}} массивы потенциаловпотенциал.
<tex> \mathtt{p[0 \dots m]} </tex> {{---}} массив паросочетания. Для каждого стобца <tex> \mathtt{i = 0 \dots m} </tex> он хранит номер соответствующей выбранной строки <tex> \mathtt{p[i]} </tex> (или <tex> \mathtt{0} </tex>, если ничего не выбрано). Полагаем, что <tex> \mathtt{p[0]} </tex> равно номеру рассматриваемой строки.
помечаем посещенными столбец ''j0'' и строку ''i0''
пересчитываем массив ''minv'', находим в нем минимум ''<tex> \delta </tex>'' и столбец ''j1'', в котором он достигнут
производим пересчет потенциалов потенциала ''u'' и ''v'' и , соответствующее изменение ''minv''
если нашли свободный столбец {{---}} выходим из цикла
ищем увеличивающуюся цепочку, пользуясь массивом предков ''way''
