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