Изменения
→Решение
== Решение ==
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - . Cеть]]
Сведем эту задачу к поиску максимального потока в сети, построенной указанным ниже образом.
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (n^3(\log(n) + \log(\cfrac{1}{\varepsilon}) + \log(\max\limits_{j=1 \ldots n} (p_j))) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n\max\limits_{j=1 \ldots n} (p_j)</tex>
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]