\Section{MincostFlow}{15 аперля}{Гусев Андрей}

\THE{Задача}

Найти поток минимальной стоимости, любого размера.

\Subsection{Алгоритм первый, простейший.}

Будем находить и добавлять к потоку путь минимального веса, пока этот вес отрицателен.

\begin{proof}
	По сути мы перебираем $k$ и выбираем лучший из Mincost k-flow. Поскольку веса кратчайших путей монотонно возрастают, $\exists k_0 \colon \forall k < k_0\ minpath[k] < 0, \forall k > k_0\ minpath[k] > 0$. 
	Следовательно, Mincost k-flow до некоторого $k_0$ монотонно убывает, а потом монотонно возрастает. Алгоритм находит это $k_0$.
\end{proof}

\Subsection{Алгоритм второй, бинпоиск по ответу.}

Поскольку мы ищем минимальное значение аргумента, для которого функция положительна, можно делать это двоичным поиском.

Найдём бинпоиском $\min k\colon w(k) > w(k + 1)$.

Время работы: $O(BS \times (MincostKFlow + FB))$, где BS -- бинпоиск, а FB -- алгоритм Форда-Белллмана.

\Subsection{Первый быстрый алгоритм.}

Возьмём алгоритм Клейна и заменим поиск отрицательного цикла на поиск цикла минимального среднего веса. Будем повторять до тех пор, пока этот средний вес отрицателен.

Время работы: $O(nm\log (nC))$, где $C$ -- минимальный вес ребра. Без доказательства.

\Subsection{Второй быстрый алгоритм. Capacity Scaling.}
Снова сведём задачу поиска минимального потока к задаче поиска минимальной циркуляции, добавив ребро t->s бесконечной пропускной способности и нулевого веса.
\begin{MyList}
	\item
	Создадим граф $G$, который будет отличаться от исходного тем, что все пропускные способности будут нулевыми.
	\item
	Пройдём циклом по $k$ от $\log C$ до 0, где C -- максимальная пропускная способность ребра.
	\item
	На каждом шаге пройдём по всем рёбрам $e$ и для каждого проверим, стоит в $k$-м разряде двоичного представления $c(e)$ 0 или 1.
	\item
	Если в $k$-м разряде 1, увеличим пропускную способность $e$ в  $G$ на $2^k$.
	\item
	Возможно, увеличение пропускной способности ребра e в G привело к появлению отрицательного цикла. Для того, чтобы проверить, произошло это или нет, найдём алгоритмом Форда-Беллмана минимальный путь из b в a.
	\item
	Если w(b->a) + w(e) < 0, то отрицательный цикл замкнулся. В таком случае пустим по нему поток размера $2^k$.
\end{MyList}

\begin{proof}
	Докажем оптимальность выбранной циркуляции для графа, полученного последним увеличением пропускной способности.
	
	Разность оптимальных циркуляций в новом и старом графе состоит из циклов, проходящих по e, т.е. набор единичных путей b->a + много раз взятое e. Очевидно, что циклов (и путей) не более $2^k$. $2^k$ путей найдётся, поскольку пропускные способности всех существующих в G рёбер кратны $2^k$.
\end{proof}

Время работы: (поиск путей) $* m * \log C$. Если искать пути алгоритмом Форда-Беллмана, получится $O*(nm^2\log C)$. Можно искать пути алгоритмом Гольдберга за $O(m\sqrt n \log С)$, и тогда время составит $O(m^2\sqrt n \log^2 C)$, но на практике выйгрыш во времени небольшой, а код заметно усложняется, и поэтому чаще используется Форд-Беллман.

Псевдокод:
\begin{code}
for (k = 30; k >= 0; --k)
  for e: edges
    if (e.capacity & 2^k)
      add_in_g(e, 2^k)
      fb(b)
      if (b->a && w(b->a) + w(e) < 0)
        inc_flow(2^k, b->a + e)
\end{code}

\Subsection{Ускорение с помощью Дейкстры с потенциалами.}

Базовый алгоритм и алгоритм с Capacity Scaling используют поиск кратчайшего пути между двумя вершинами. 
Эффективно решать задачу поиска кратчайшего пути в орграфе позволяет алгоритм Дейкстры. В случае поиска MincutFlow с алгоритмом Дейкстры возникает проблема: 
мы умеем применять алгоритм Дейкстры на графах с отрицательными рёбрами с помощью потенциалов, но мы не готовы к появлению в графе новых отрицательных рёбер, 
а появляться при добавлении потока они могут. Решим проблему прибавлением к потенциалу вершины расстояния до неё на каждой итерации.

$d[b] - d[a] \le w(e)$ (иначе расстояние до b можно уменьшить через e) $\rightarrow d[a] + w(e) - d[b] \ge 0 \rightarrow$ веса с новыми потенциалами неотрицательны.

Псевдокод:
\begin{code}
d`$_0$`=FB
for i = 1..k
  (d`$_1$`, path) = Djkstra(d`$_0$`)
  d`$_0$` += d`$_1$`
\end{code}
