Hardprob/Maximum Priority Flow
Материал из DISCOPAL
Версия от 22:38, 8 апреля 2023; StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --> * Направленный граф <m>G=\left(V,E\right)</m>, вершины-источники <m>s_1, \ldots, s_k \in V</m>, вершины-ст…»)
- Направленный граф , вершины-источники , вершины-стоки , емкость ребер , ограничения на вершинах , и для любой вершины v, есть некий порядок исходящих ребер.
- Найти приоритетный поток f, т.е. функция , такая что
- для любого ребра e,
- для любой вершины , поток сохраняется в v
- для любой вершины v
- поток покидающий v не превышает b(v)
- для исходящей любой пары ребер , если и , то .
- Максимизировать поток, приходящей в первый сток , т.е. .
Код в «maximum-priority-flow.ipynb» на гитлаб или живьем в лабе
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.