3622
правки
Изменения
м
→Описание алгоритма
* '''Шаг 0.''' Введем ''следующее понятие'':
: Назовём потенциалом два произвольных массива чисел <tex> u[1 \ldots n] </tex> и <tex> v[1 \ldots n] </tex> таких, что выполняется условие:
<center> <tex> u[i] + v[j] \leqslant a[i][j] ~ (i = 1 \ldots n)</tex>, где <tex> a </tex> {{---}} заданная матрица . </center>
* '''Шаг 1.''' Добавляем в рассмотрение очередную строку матрицы <tex> a. </tex>
* '''Шаг 2.''' Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.
