\Section{Потоки: LR.}{12 апреля}{Богомолов Егор}

\Subsection{Что хотим?}

\begin{Def}
LR-поток --- $\forall e \in Edges \colon L_e \leq flow_e \leq R_e$
\end{Def}

Варианты задач:

\begin{MyList}
\item Найти какой-нибудь корректный поток.
\item Найти максимальный.
\item Естественным образом обобщается на mincost, об этом в других сериях.
\end{MyList}

\vspace*{-0.5em}
\Subsection{Понемногу двигаемся к цели}
\vspace*{-0.5em}

\begin{MyList}

\item Научимся искать поток в графе с несколькими истоками и стоками. Для этого добавим фиктивные исток и сток. Из фиктивного истока проведем ребра бесконечной пропускной способности во все реальные, из всех реальных стоков --- бексонечные ребра в фиктивный сток. Найдем поток между фиктивными.

\item Решим такую задачу: в городе есть заводы и магазины. Они соединены дорогами, у каждой есть пропускная способность. Про заводы известно, сколько товара они производят, про магазины --- сколько продают. Требуется составить такой план перевозок, что весь товар будет продан и ни в одном магазине не будет нехватки товара.

	Нарисуем граф, вершинам сопоставим значения --- избытки (положительные) и недостатки (отрицательные) товара. Создадим фиктивный исток, из него проведем во все вершины с избытком ребра величины, равной избытку. Создадим фиктивный сток, в него проведем ребра из всех вершин с недостатком величины, равной модулю недостатка. Найдем максимальный поток в этом графе, он и будет ответом (в случае, если он насытил все ребра из истока и все ребра в сток).

\item Теперь пусть появятся величины $L_e$ и $R_e$. Пусть $e.from = a, e.to = b$. Тогда добавим в вершине $a$ избыток $L_e$, а в $b$ --- недостаток $L_e$. $e$ зададим пропускную способность $(R_e - L_e)$. Что мы сейчас сделали? Свели задачу о LR-циркуляции (т.к. у нас нет истока и стока, это циркуляция, а не поток) к задаче из предыдущего пункта.

\item А теперь сведем задачу о LR-потоке к LR-циркуляции. Просто добавим бесконечное ребро из стока в исток.

\item Какой-нибудь нашли, но что делать дальше?

\end{MyList}

\vspace*{-0.5em}
\Subsection{Максимизируем}

Ищем LR-поток. Пусть $f$ --- найденный нами поток, $f^{max}$ --- какой-нибудь максимальный LR-поток. Рассмотрим $(f^{max} - f)$, это обычный поток в $G_f$ (напоминаю, что так мы обозначаем остаточную сеть потока $f$). 

Взглянем на какое-нибудь ребро, скажем, $e$. Про него верны следующие неравенства:
$$
L_e \leq f^{max}_e \leq R_e
$$
$$
L_e \leq f_e \leq R_e
$$
$$
D_e = L_e - f_e  \leq f^{max}_e - f_e \leq R_e - f_e = U_e
$$

Остаточная сеть. В ней концы $e$ соединены ребрами пропускной способности $U_e$ в прямую и $-D_e$ в обратную сторону. 
Если $f \neq f^{max}$, то выходит, что в остаточной сети есть дополняющий путь (по пути все $U_e > 0$, a $D_e \leq 0$ всегда). 
Значит, можно просто искать дополняющие пути для максимизации, что делали и с обычным. Получается, что LR-поток ищем за то же время, что и обычный --- $\O(flow)$.

\Subsection{Не забываем старые знания.}

В алгоритме Диница много времени занимает пускание потока по ней. Почему много? Потому что по одним и тем же ребрам, у которых от запуска к запуска пропускная способность остается положительной, мы можем ходить много-много раз. На помощь приходит link-cut tree! Будем поддерживать сеть сперва как лес (конечно же link-cut деревьев). Какие операции нужно будет реализовывать? 

\begin{MyList}
\item	Искать минимум на пути и его позицию, чтобы находить ребра, которые насытятся на данном запуске. 
\item	Добавлять на пути (собственно запуск потока). 
\item	Удалять ребро, если насытилось.
\end{MyList}

	Когда решаем найти очередной путь, из вершины ходим не по отдельным ребрам, а сразу переходим в корень ее компоненты в link-cut-е. 
	Получается быстро, алгоритм начинает работать за $\O(VE\log V)$.

Немножко про это по ссылкам:

\url{http://math.mit.edu/~rpeng/18434/blockingFlows.pdf}

\url{http://www.arl.wustl.edu/~jst/cse/542/text/sec19.pdf}


