Изменения

<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> равно номеру рассматриваемой строки.

<tex> \mathtt{minv[j] = \min_min\limits_{i \in Z_1}\{(a[i][j] - u[i] - v[j]\})} </tex>

'''for''' i = 1 '''to''' n p[0] = i j0 = 0// рассматриваем строки матрицы ''a'' заполняем массивы '''minv''' {{---}} <tex> \infty </tex>, '''used''' {{---}} false ''false'while''' true used[j0] = true i0 = p[j0] <tex> \delta </tex> = <tex> \infty </tex> '''forwhile''' j = 1 ''true'to''' m// ищем свободный столбец помечаем посещенными столбец ''j0'if'и строку '' used[j] == 0 cur = a[i0][j] - u[i0] - v[j] '' пересчитываем массив 'if''' cur < minv[j] minv[j] = cur way[j] = j0 '', находим в нем минимум 'if''' minv[j] < <tex> \delta </tex> <tex> \delta </tex> = minv[j] j1 = j ''и столбец 'for'j1'' j = 0 '''to''' m, в котором он достигнут производим пересчет потенциалов ''u'if'и '' used[j] u[p[j]] += <tex> \delta </tex> v[j] -= <tex> \delta </tex> ''и соответствующее изменение 'else'minv'' minv[j] если нашли свободный столбец {{---= <tex> \delta </tex> j0 = j1 '''if''' p[j0] != 0 '''break'''}} выходим из цикла ищем увеличивающуюся цепочку, пользуясь массивом предков '''while''' true j1 = way[j0] p[j0] = p[j1] j0 = j1 '''if''' j0 <tex> \neq </tex> 0 '''break'''