\Start{Потоки}{17 ноября}{Копелиович Сергей}

\Section{Flows}

\Subsection{Определения}

Пусть дан ориентированный граф $G$ из $n$ вершин и $m$ рёбер.
Между каждыми двумя вершинами $v$ и $u$ графа $G$ есть ребро с пропускной
способностью $c_{v,u} \ge 0$. Если мы хотим, чтобы ребра не было, скажем $c_{v,u} = 0$.

\begin{Def}{Поток из $s$ в $t$} --
  функция $f_{v,u} \in \R$, обладающая тремя свойствами

  \begin{MyList}[0pt]
    \item $\forall v, u \quad f_{v,u} \le c_{v,u}$ (течёт не больше пропускной способности)
    \item $\forall v, u \quad f_{v,u} = {-}f_{u,v}$ (антисимметричность)
    \item $\forall v \not= s, t \quad \sum_u f_{v,u} = 0$ (сохранение потока)
  \end{MyList}
\end{Def}

При этом вершина $s$ называется {\it истоком}, а вершина $t$ {\it стоком}.

Иногда мы будем писать $f_e$ и $c_e$ -- поток и пропускная способность для ребра $e$.

\begin{Def}{Разрез между $s$ и $t$} --
  разбиение множества вершин $V \colon V = S \sqcup T, s \in S, t \in T$.\\
  ($S \cap T = \varnothing$, исток лежит в $S$, сток лежит в $T$)
\end{Def}

Разрез будем обозначать $(S, T)$.

\begin{Def}{Величина потока $|f| = \sum_v f_{s,v}$ (сумма вытекающего из истока $s$).}\end{Def}

Величина потока может получиться отрицательной. Определениям это не противоречит.

\begin{Def}{Величина разреза $C(S, T) = \sum\limits_{v \in S, u \in T} c_{v, u}$} (сумма пропускных способностей рёбер, проходящих через разрез).\end{Def}

\begin{Def}{Обозначение $F(A, B) = \sum\limits_{v \in A, u \in B} f_{v, u}$}\end{Def}

Это лишь обозначение. $A$ и $B$ могут пересекаться или даже совпадать.

\begin{Def}{Максимальный поток} -- $f \colon |f| = \max$\end{Def}

\begin{Def}{Минимальный разрез} -- $(S,T) \colon C(S, T) = \min$\end{Def}

\begin{Def}{Ребро насыщенно $\EQ$ поток по ребру равен его пропускной способности}\end{Def}

\begin{Def}{Остаточная сеть $G_f$ -- граф из рёбер, для которых $c_{u,v} - f_{u,v} > 0$}.
Иногда в остаточной сети так же определяют пропускные способности рёбер: $c_{u,v} - f_{u,v}$
\end{Def}

\begin{Def}{Дополняющий путь} -- путь из $s$ в $t$, для всех рёбер которого $f_{v,u} < c_{v,u}$.
Иначе говоря ``путь в остаточной сети''\end{Def}

\begin{Def}{Циркуляция -- поток размера ноль.}\end{Def}

Например, цикл является циркуляцией.

\pagebreak

\vspace*{-2em}
\Subsection{Теорема и алгоритм Форда-Фалкерсона}

\begin{Lm}{Величина потока равна потоку, протекающему через разрез:}\\
$\forall \text{ разрез } (S, T), \forall \text{ поток } f \quad |f| = F(S, T)$
\begin{proof}{\small $|f| = F(\{s\}, V) = F(S, V) = F(S, S) + F(S, T) = 0 + F(S, T) = F(S, T)$}\end{proof}
\end{Lm}

\begin{Lm}{Поток не больше разреза:}
\label{Lm:FlowCut}
$\forall \text{ разрез } (S, T), \text{ поток } f \quad |f| \le C(S, T)$
\begin{proof}{\small $|f| = F(S, T) \le C(S, T)$}\end{proof}
\end{Lm}

\begin{Lm}{\it О дополняющем пути.} Если есть дополняющий путь, поток не максимален.\end{Lm}
\begin{proof}
Пусть есть дополняющий путь: увеличим поток по прямым рёбрам, уменьшим по обратным.
Все 3 свойства потока выполняются, размер увеличился.
\end{proof}

\THEE{Алгоритм Форда-Фалкерсона.} \\
Алгоритм ищет максимальный поток в графе с целочисленными пропускными способностями.

\begin{MyTabbing}
$f \leftarrow 0$ \\
\t{while} существует дополняющий путь: \\
\> ищем его поиском в глубину по ненасыщенным рёбрам \\
\> пусть путь: $s = v_1, v_2, \dots, v_k = t$\\
\> $x = \min_{i=1..k{-}1}\bigl[c_{v_{i{+}1},v_i} - f_{v_{i{+}1},v_i}\bigr]$ ($x > 0$; $x = $ сколько потока можно толкнуть по пути)\\
\> увеличим поток по пути на $x$\\
\t{return} $f$ 
\end{MyTabbing}

Если $c_{v,u}$ целые, то $x \ge 1$, поэтому алгоритм работает работает за конечное время.
Максимальность потока будет следовать из следующей теоремы:

\begin{Thm}{\bf Форда-Фалкерсона.} \quad $\max |f| = \min C(S, T)$.\end{Thm}
\begin{proof}
  Для доказательства предъявим разрез и поток одинакового размера, 
  из этого по \autoref{Lm:FlowCut} будет следовать, что поток максимален, а разрез минимален.
  Возьмём поток, полученный алгоритмом Форда-Фалкерсона, запустим \t{dfs} из истока $s$ по рёбрам, по которым можно увеличить потока ($f_{u,v} < c_{u,v}$).
  Такой \t{dfs} отработает за время $\O(n + m)$, до $t$ он не дойдёт, так как дополняющих путей нет.
  Вершины графа разбились на посещённые \t{dfs}-ом -- $S$, и непосещённые -- $T$. 
  Заметим, что все рёбра из $a \in S$ в $b \in T$ обладают свойством, что $f_{a,b} = c_{a,b}$,
  иначе \t{dfs} прошёл бы по ребру и посетил бы $b$.
  Поэтому $F(S, T) = C(S, T) \SO |f| = C(S, T)$.
\end{proof}

\begin{Rem} Поиск минимального разреза.\\ 
Мы научились по готовому максимальному потоку за $\O(n + m)$ искать минимальный разрез.\end{Rem}

Время работы алгоритма Форда-Фалкерсона равно $\O(|f| \cdot m)$, но зачастую гораздо меньше.
Тем не менее, помните, существуют тесты, на которых даже Форд-Фалкерсон с разндомизированным \t{dfs} (перебирает рёбра в случайном порядке)
работает экспоненциальное от $n$ время.

\vspace*{0.5em}
Алгоритм Форда-Фалкерсона применим для целочисленных пропускных способностей.
Для вещественных весов он может работать бесконечно долго.

\Subsection{Задачи}

\THEE{Задача о максимальном паросочетании в двудольном графе} \\
Решается поиском потока за $\O(nm)$. 
Добавим исток к первой доли, сток ко второй, найдём максимальный поток. $|f| \le n$. Рёбра двудольного графа, по которым течёт поток -- максимальное паросочетание.

\THEE{Задача о восстановлении матрицы} \\
Даны суммы в строках и столбцах квадратной матрицы и информация, что все числа в матрице от $0$ до $100$.
Задача: восстановить любую возможную матрицу.
Решение: исток, первая доля -- строки, вторая доля -- столбцы. Рёбра из истока в строки имеют пропускную способность ``сумма в стороке'',
аналогично рёбра из столбцов в сток. Клетке матрицы соответсвует ребро между строкой и столбцой, имеющее пропускную способность $100$.
Найдём в полученномм графе максимальный поток.
Если все рёбра из истока и в сток насыщенны, матрица существует, матрицу задают величины потоков по рёбрам, соответсвуещим клеткам.

\THEE{Задача о посадке людей в самолёты} \\
Даны самолёты, у каждого есть вместимость $k_i$ и время вылета $t_i$. Даны люди, у каждого
есть диапазон времён $[l_i..r_i]$, когда человек хочет улететь. Задача: распределить всех людей по самолётам.
Строим граф: из истока в людей пропускная способность 1, из людей, в подходящие им самолёта пропускная способность 1, из самолётов в сток пропускная способность $k_i$.

\Subsection{Реализация}

\begin{example}\label{exm:flowcode}
На практике, чтобы \t{dfs} работал за $\O(n + m)$ хранят не матрицу смежности, а список рёбер.
Чтобы выполнялась антисимметричность потока, для каждого ребра есть обратное ему.
\end{example}
\begin{code}
struct Edge {
  int from, to; // `ребро из from в to`
  int next; // `номер следующего ребра из вершины from`
  int f; // `flow (поток)`
  int c; // `capacity (пропускная способность)`
};
int n, m;
vector<Edge> edges;
vector<int> head; // `для каждой вершины номер первого ребра, начало списка`

void add_edge( int a, int b, int capacity ) {
  edges.push_back(Edge {a, b, head[a], 0, capacity});
  head[a] = edges.size() - 1;
}
void read() {
  cin >> n >> m; // `количество вершин, количество рёбер`
  edges.reserve(2 * m); // `каждому ребру нужно обратное`
  head = vector<int>(n, -1); // `-1 обозначает пустой список`
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c, a--, b--; // `во входных данных вершины обычно нумеруются с 1`
    add_edge(a, b, c); // `прямое ребро`
    add_edge(b, a, 0); // `обратное ребро`
  }
}
\end{code}

Теперь у ребра номер \t{i} есть обратное \t{i\XOR 1},
а чтобы перебрать рёбра из вершины \t{i} следует начать с ребра \t{head[i]}, получится
\lstinline`for (int e = head[i]; e != -1; e = edges[e].next)`.
В алгоритме Форда-Фалекрсона после того, как мы нашли путь, нужно увеличить по нему поток, это
можно делать на обратном ходе \t{dfs}-а (возврат из рекурсии).

\begin{code}
int cc;
vector<int> u; // `Если u[i] = cc, вершина помечена, иначе не помечена`

int dfs( int v, int flow ) {
  if (v == t)
    return flow;
  u[v] = cc; // `dfs должен работать за линейное время, каждую вершину посещаем один раз`
  for (int x, i = head[v]; i != -1; i = edges[e].next) {
    Edge &e = edges[i];
    if (e.f < e.c && u[e.to] != cc && (x = dfs(e.to, min(flow, e.c-e.f))) > 0) {
      e.f += x, edges[i ^ 1].f -= x; // `увеличили по прямому, уменьшили по обратному`
      return x;
    }
  }
  return 0;
}
int maxFlow() {
  read();
  cc = 1, u = vector<int>(n, 0);
  int f = 0, add;
  while ((add = dfs(s, INT_MAX)) > 0)
    f += add, cc++; // `cc++ делает все вершины не помеченными`
  return f;
}
\end{code}

\vspace*{0.3em}
Оптимизации:
\begin{MyList}[0pt]
  \item Можно вместо \t{f} и \t{c} хранить сразу \t{c - f}.
  \item Почти всегда можно не хранить \t{from}.
\end{MyList}
\vspace*{-0.8em}

\THEE{Замечение:} Без обратных рёбер бы алгоритм не работал:

\begin{center}\includegraphics[width=5cm]{pics/1.png}\end{center}

Если бы первый \t{dfs} нашёл красный путь, второй \t{dfs} без обратных рёбер не смог бы найти путь.
А с обратными смог бы найти вот такой синий путь:

\begin{center}\includegraphics[width=5cm]{pics/2.png}\end{center}

\pagebreak

\vspace*{-2em}
\Subsection{Декомпозиция потока на пути}

\THEE{Декомпозиция потока на пути}. \\
Заметим, что путь из $s$ в $t$, по которому течёт $x$ единиц потока,
можно рассматривать, как поток размера $x$.
Алгоритм Форда-Фалкерсона работает по принципу ``сложим маленькие потоки-пути, получим большой поток''.
Теперь рассмотрим обратную задачу: 

\begin{Def}{Задача декомпозиции: дан поток, представить его в виде объединения путей и циркулцяции с дополнительным
ограничением ``в декомпозиции не должно быть взаимно обратных рёбер''. }
\end{Def}

То есть красный и синий путь на картинке выше не являются корректной декомпозицией.

Алгоритм поиска: очередной путь отщепляем \t{dfs}-ом по рёбрам с ненулевым потоком.

\begin{code}
int getPath( int v, int flow ) {
  if (v == t)
    return flow;
  u[v] = cc; 
  for (int x, i = head[v]; i != -1; i = edges[e].next) {
    Edge &e = edges[i];
    if (e.f > 0 && u[e.to] != cc && (x = getPath(e.to, min(flow, e.f))) > 0) {
      e.f -= x, edges[i ^ 1].f += x; // `отщепили путь`
      return x;
    }
  }
  return 0;
}
\end{code}

Время работы такого алгоритма $\O(m^2)$, так как \t{getPath} работает за $\O(m)$, 

и после каждого вызова \t{getPath} увеличивается количество рёбер с нулевым $f_e$. 

{\it Упражнение:} улучшить время декомпозиции до $\O(nm)$.

\Subsection{Задача про $k$ путей}

Теперь, когда мы умеем раскладывать поток на пути, можно решить следующие задачи:
\begin{MyList}[0pt]
  \item Найти в орграфе $k$ непересекающихся по рёбрам путей из $s$ в $t$.
  \item Найти в неорграфе $k$ непересекающихся по рёбрам путей из $s$ в $t$.
  \item Найти в орграфе $k$ непересекающихся по вершинам путей из $s$ в $t$.
  \item Найти в неорграфе $k$ непересекающихся по вершинам путей из $s$ в $t$.
\end{MyList}
Все задачи решаются за $\O(km)$: сперва запускаем Форда-Фалкерсона, затем декомпозицию потока.
Чтобы работать с неориентированным графом нужно неориентированное ребро представить, как два ориентированных.
Чтобы пути непересекались по вершинам, научимся раздваивать вершину:

\vspace*{-2em}
\newlength{\mywidth}
\setlength{\mywidth}{100pt}
\begin{center}
\begin{tabular}{p{\mywidth}p{0.5 \mywidth}p{\mywidth}}
  %\hline
    \vspace{-0.3em}
    \includegraphics[width=\mywidth]{pics/5.png}
    \vspace{-1em}
    %\begin{center}{Несвязный результат} \end{center}
  &
  \begin{center}
    {\Huge $\longrightarrow$}
  \end{center}
  &
    \vspace{-0.3em}
    \includegraphics[width=\mywidth]{pics/6.png}

    \vspace{-1em}
    %\begin{center}{Лишнее ребро}\end{center}
  \\
  %\hline
\end{tabular} 
\end{center}
\vspace*{-1em}

В графе с раздвоенными вершинами пути, непересекающиеся по рёбрам, непересекаются по вершинам в исходном графе.

\pagebreak

\vspace*{-2em}
\Subsection{Несколько стоков и истоков}

Пусть мы хотим найти несколько непересекающихся путей. Каждый должен начинаться в одной из вершин множества $A$ 
и заканчиваться в вершинах множества $B$. То есть, нас просят найти поток на графе
с несколькими истоками и стоками. Добавим исток: вершину $s$ и рёбра из $s$ в $A$. Добавим сток: вершину $t$ и рёбра из $B$ в $t$.
Будем искать поток из $s$ в $t$.

\Subsection{Алгоритмы поиска потока}

\begin{example}\label{exm:edmonds}
\THEE{Алгоритм Эдмондса-Карпа} -- вместо \t{dfs} (поиск в глубину) используем \t{bfs} (поиск в ширину).
Оказывается, количество дополняющих путей в таком случае не более $\mfrac{nm}{2}$, поэтому алгоритм работает за $\O(nm^2)$ и подходит для графов с вещественными весами.
\end{example}

\vspace*{0.5em}
Время работы оставим без доказательства, его можно посмотреть в \href{http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%AD%D0%B4%D0%BC%D0%BE%D0%BD%D0%B4%D1%81%D0%B0-%D0%9A%D0%B0%D1%80%D0%BF%D0%B0}{ИТМО-конспектах} 

\THEE{Алгоритм масштабирования потока} (Scaling) -- будем искать дополняющие пути, по которым можно увеличить поток хотя бы на $k = 2^t$.
Для этого в \t{dfs} главный \t{if} поменяем вот так:\\
\lstinline|if (e.f + k <= e.c && u[e.to] != cc && (x = dfs(e.to, min(flow, e.c - e.f))) > 0) {|\\
А поиск потока теперь выглядит так:
\begin{code}
int maxFlow() {
  read();
  cc = 1, u = vector<int>(n, 0);
  // MAX_CAPACITY <= 2^t <= 2*MAX_CAPACITY
  for (int k = (1 << t); k > 0; k = k / 2, cc++) 
    while ((add = dfs(s, k, INT_MAX)) > 0)
      f += add, cc++;
  return f;
}
\end{code}

\begin{Thm}
Время работы Scaling алгоритма поиска потока на графе с целочисленными пропускными способностями
равно $\O(m^2 \log U)$, где $U$ -- максимальная пропускная способность.
\end{Thm}
\begin{proof}
Различных $k$ мы переберём $\log U$ штук, \t{dfs} работает за $\O(m)$, осталось
показать, что для каждого $k$ мы найдём $\O(m)$ путей. Для этого
обозначим за $f_1$ поток до поиска путей размера $k$, а за $f_2$ поток после того, как все пути размера $k$ найдены.
$f_1$ обладает свойством ``нет дополняющих путей размера $2k$'', значит, есть такой разрез, что для всех рёбер, проходящих через разрез, $c_e - f_e < 2k$.
Посмотрим на декомпозицию потока $f_2 - f_1$ на пути. Каждый такой путь имеет размер не меньше $k$ и проходит через разрез.
Получаем, что путей не больше чем $\mfrac{m \cdot 2k}{k} = 2m = \O(m)$.
\end{proof}

\THEE{Замечание.} На самом деле на практике алгоритм работает за $\O(m^2)$. ;)

\pagebreak

\vspace*{-2em}
\Subsection{Реклама}

Из крутых и при этом не сложных алгоритмов так же стоит заметить:
\begin{MyList}[0pt]
  \item \href{https://en.wikipedia.org/wiki/Dinic%27s_algorithm}{Алгоритм Диница}
    \begin{InnerMyList}
      \item Ищет поток за $\O(n^2m)$, при соединении с идеей scaling даже за $\O(nm \log U)$.
      \item  Позволяет искать паросочетание за $\O(m\sqrt{n})$, использование алгоритма Диница для поиска паросочетание в двудольном графе называется
        алгоритмом Хопкрофта-Карпа.
      \item Позволяет искать поток в сетях с единичными пропускными способностями за $\O(\min(m^{1/2},n^{2/3})m)$.
    \end{InnerMyList}
  \item Семейство алгоритмов поиска потока, основанных на идее поиска предпотока (preflow), и использующих идею global relabeling.
    Такие алгоритмы хорошо себя ведут на практике. Не хуже $nm$.
  \item Алгоритм от Ahuja и Orlin 1992-го года, позволяеющей с помощью идей предпотока и масштабирования избытка искать поток за $\O(nm + n^2\log U)$.
\end{MyList}

\Section{Mincost Flows}

\Subsection{Формулировка задачи}

Дан ориентированный взвешенный граф. $w_e$ -- вес ребра. 
При поиске потока у каждого ориентированного ребра $e$ есть обратное ребро $e'$.
Мы уже знаем, что $f_e = {-}f_{e'}$.
Определим вес обратного ребра равным ${-}w_e$.
Теперь для потока $f$ определим вес $W(f) = \mfrac{1}{2}\sum_e f_ew_e$. 
Заметим, что $W(f) = \sum_{e \in E} f_ew_e$, где $E$ -- множество прямых рёбер.\\
Обозначение $W(x)$ будем применять не только к потокам.\\
Если $p$ -- путь, $W(p)$ -- вес пути. Если $z$ -- циркуляция, $W(z)$ -- вес циркуляции.

\THE{Min cost flow:} найти поток $f \colon W(f) = \min$

\vspace*{-0.3em}
\THE{Min cost max flow:} найти поток $f \colon |f| = \max, W(f) = \min$

\vspace*{-0.3em}
\THE{Min cost k-flow:} найти поток $f \colon |f| = k, W(f) = \min$

\Subsection{Алгоритм поиска min cost k-flow}

\vspace*{-0.3em}
\begin{Lm}
\label{lm:NoCycles}
Если в остаточной сети есть отрицательный цикл, поток не mincost
\end{Lm}
\begin{proof}Пусть $C$ -- отрицательный цикл, заменим $f$ на $f + C$ (увеличим поток по циклу). Размер не изменился, вес уменьшился.\end{proof}

\begin{Lm}
Если в остаточной сети нет отрицательных циклов, поток mincost
\label{lm:MinCost}
\end{Lm}
\begin{proof}
Пусть есть наш поток $f_1$ и поток $f_2 \colon |f_1| = |f_2|, W(f_1) > W(f_2)$,
рассмотрим поток $h = f_2 - f_1$ в сети $G_{f_1}$. Это корректный поток, так как $(f_2-f_1)_e \le (c - f_1)_e$.
$|h| = 0$, $W(h) < 0$, то есть перед нами отрицательная циркуляция. Осталось заметить, что так же, как поток можно
разбить на пути и циркуляцию, циркуляцию можно разбить на циклы, один из них будет отрицательным.
\end{proof}

\begin{Lm}Обозначим за $f_k$ mincost k-flow. Тогда $f_{k{+}1} = f_k + \t{shortestPath} + \t{zeroCirculation}$.\end{Lm}
\begin{proof}
Рассмотрим поток $h = f_{k{+}1} - f_k$ в $G_{f_k}$. $|h| = 1$, декомпозиция $h$ -- это путь $p$ плюс циркуляция $z$.
Из того, что $f_{k{+}1}$ mincost, имеем $W(z) \le 0$, а $W(p) = W(\t{shortestPath})$. 
По лемме \autoref{lm:NoCycles} имеем $W(z) \ge 0 \SO W(z) = 0$.
\end{proof}

\vspace*{-0.3em}
\THEE{Алгоритм поиска mincost k-flow в графе без отрицательных циклов}
\begin{MyTabbing}
$f \leftarrow 0$ (нет отрицательных циклов) \\
for i=1..k: \\
\> ищем Форд-Беллманом кратчайший путь \\
\> увеличим поток по пути на $1$\\
\t{return} $f$ 
\end{MyTabbing}

Алгоритм работает за $\O(knm)$.

\vspace*{0.5em}
Обозначим $d_k = W(f_{k{+}1}) - W(f_k)$ (вес $k$-го дополняющего пути).
Из доказательства алгоритма Эдмондса Карпа [\ref{exm:edmonds}] следует, что $d_{k{+}1} \ge d_k$.
Поэтому можно соптимизировать: толкать не единицу потока, а столько, сколько сможем, $\min_{e \in path} (c_e - f_e)$.

\pagebreak

\vspace*{-2em}
\Subsection{Алгоритм поиска mincost flow}

Мы уже знаем, что $d_{k{+}1} \ge d_k$.
Вес потока уменьшается, пока $d_k < 0$.

Алгоритм: начинаем с $f_0$, наращиваем поток, пока $d_k < 0$.

Время работы $\O(nm|f|)$, где $|f|$ -- размер искомого потока. 

\Subsection{Реализация mincost flow}

Модифицируем код [\ref{exm:flowcode}], получим
\begin{code}
void add_edge( int a, int b, int capacity, int weight ) {
  edges.push_back(Edge {a, b, head[a], 0, capacity, weight});
  head[a] = edges.size() - 1;
}

queue<int> q;
void relax( int v, int d ) {
  if (dist[v] > d)
    return;
  dist[v] = d;
  if (!in_queue[v])
    q.push(v), in_queue[v] = 1;
}
bool ford_bellman() {
  const int infty = 1e9; 
  for (int i = 0; i < n; i++)
    dist[i] = infty, in_queue[i] = 0;
  relax(s, 0);
  while (q.size()) {
    int v = q.front(); q.pop();
    in_queue[v] = 0;
    for (int i = head[v]; i != -1; i = edges[e].next) {
      Edge &e = edges[i];
      if (e.f < e.c)
        relax(e.to, d[v] + e.weight);
    }
  }
  return dist[t] < infty;
}
...
add_edge(a, b, c, w); // `прямое ребро`
add_edge(a, b, 0, -w); // `обратное ребро`
\end{code}

Данная реализация Форд-Беллмана в худшем случае использует $\O(n)$ дополнительной памяти
и $\O(nm)$ времени. В среднем работает за $\O(m)$.
Называется эта реализация ``Форд-Беллман с очередью'' или ``\href{http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm}{Shortest Path Faster Algorithm}'' (SPFA).
Не путайте, пожалуйста, эту реализацию с алгоритмом Левита, который добавляет в начало очереди.

\pagebreak

\vspace*{-2em}
\Subsection{Отрицательные циклы}

Если в графе есть отрицательные циклы, $f_0 \not= 0$.
Чтобы найти $f_0$, воспользуемся леммами \autoref{lm:NoCycles} и \autoref{lm:MinCost}. Начнём с пустого потока, пока
в остаточной сети $G_f$ есть отрицательный цикл, увеличим поток по циклу. Отрицательный цикл можно искать за $\O(nm)$
с помощью алгоритма Форда-Беллмана.

\vspace*{0.5em}
Так можно искать не только $f_0$, но и $f_k$.

\THEE{Другой алгоритм поиск mincost k-flow}
\begin{InnerMyList}
  \item Найдём какой-нибудь поток размера $k$ любым алгоритмом поиска потока.
  \item Пока в остаточной сети есть отрицательный цикл, увеличим поток по циклу.
  \item Если нет отрицательных циклов, по лемме \autoref{lm:MinCost} поток mincost.
\end{InnerMyList}
\vspace*{-0.5em}
Этот алгоритм работает особенно хорошо, если искать не произвольный отрицательный цикл, а ``\href{http://webcourse.cs.technion.ac.il/236359/Spring2013/ho/WCFiles/MMC.ps}{цикл минимального среднего веса}''

\Subsection{Реклама}

Идея \href{https://en.wikipedia.org/wiki/Johnson%27s_algorithm}{потенциалов Джонсона}
позволяет Форд-Беллмана заменить на Дейкстру. 
Алгоритм поиска mincost k-flow после этого работает за $\O(km\log n)$ и даже $\O(k(m + n\log n))$.

\vspace*{0.5em}
Заметим, что мы не научились искать mincost потока за полиномиальное от $n$, $m$ и $\log U$ время.
Такие алгоритмы существуют. Самый простой из них основан на идее ``capacity scaling'' и работает за время $\O(\t{Dijkstra } m \log U)$ (столько раз запускает Дейкстру).

%\LINE
%{\Huge\bf КОНЕЦ }
