Изменения
Нет описания правки
<includeonly>[[Категория: В разработке]]</includeonly>
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1]]
==Постановка задачи==
Рассмотрим еще одну задачу на нахождение расписания:
(Б) В расширенной сети существует поток от s до t со значением <tex>\sum\limits_{i=1}^{n} p_i</tex>
}}
[[Файл:Figure_5.9.b.png|500px|thumb|right|Рис. 2.2 - Расширение сети]]
==Время работы==
Из-за максимального потока в расширенной сети могут быть рассчитаны в <tex>O (m n^3)</tex> шагов, возможность проверки может быть сделано с такой же сложности. Для решения задачи <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск. Получается алгоритм со сложностью <tex>O (mn^3(log(n) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому что <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.
