\Section{Mincost}{2 октября 2017}{Сергей Копелиович}

\Subsection {Mincost k-flow в графе без отрицательных циклов}

Сопоставим всем прямым рёбрам вес (стоимость) $w_e \in \R$.

\begin{Def}
Стоимость потока $W(f) = \sum_e w_ef_e$. Сумма по прямым рёбрам.
\end{Def}

Обратному к $e$ рёбру $\overline{e}$ сопоставим $w_{\,\overline{e}} = {-}w_e$.

\down
Если толкнуть поток сперва по прямому, затем по обратному к нему ребру, стоимость не изменится.
Когда мы толкаем единицу потока по пути \t{path}, изменение 
потока и стоимости потока теперь выглядят так:

\begin{code}
for (int e : path):
	edges[e].f++
	edges[e ^ 1].f--
	W += edges[e].w;
\end{code}

{\bf Задача mincost k-flow:} найти поток $f \colon |f| = k, W(f) \to \min$

\down
При решении задачи мы будем говорить про веса путей, циклов, ``отрицательные циклы'', кратчайшие пути...
Везде вес пути/цикла -- сумма весов рёбер ($w_e$).

\down
{\bf Решение \NO{1}.} Пусть в графе нет отрицательных циклов, а также все $c_e \in \Z$.

Тогда по аналогии с алгоритмом Ф.Ф., который за $\O(k\cdot \t{dfs})$ искал поток размера $k$,
мы можем за $\O(k \cdot \t{FordBellman})$ найти mincost поток размера $k$.
Обозначим $f_k$ оптимальный поток размера $k \SO f_0 \equiv 0, f_{k+1} = f_k + path$, где $path$ -- кратчайший в $G_{f_k}$.

\begin{Lm}\label{lm@mincost}
$\forall k, |f| = k \quad (W(f) = \min) \EQ (\nexists$ отрицательного цикла в $G_f$)
\end{Lm}
\begin{proof}
Если отрицательный цикл есть, увеличим по нему поток, $|f|$ не изменится, $W(f)$ уменьшится.
Пусть $\exists f^{*} \colon |f^{*}| = |f|, W(f^{*}) < W(f)$, рассмотрим поток $f^{*} - f$ в $G_f$.\\
Это циркуляция, мы можем декомпозировать её на циклы $c_1, c_2, \dots, c_k$. \\
Поскольку $0 > W(f^{*} - f) = W(c_1) + \dots + W(c_k)$,
среди циклов $c_i$ есть отрицательный.
\end{proof}

\begin{Thm}
Алгоритм поиска mincost потока размера $k$ корректен.
\end{Thm}
\begin{proof}
База: по условию нет отрицательных циклов $\SO f_0$ корректен.

Переход: обозначим $f^{*}_{k+1}$ mincost поток размера $k{+}1$, смотрим на декомпозицию $\Delta f = f^{*}_{k+1} - f_k$.
$|\Delta f| = 1 \SO$ декомпозиция \t{=} путь $p$ \t{+} набор циклов. Все циклы по \autoref{lm@mincost} неотрицательны $\SO$
$W(f_k + p) \le W(f^{*}_{k+1}) \SO$, добавив, кратчайший путь мы получим решение не хуже $f^{*}_{k+1}$.
\end{proof}

\begin{Lm}
Если толкнуть сразу $0 \le x \le \min_{e \in p}(c_e - f_e)$ потока по пути $p$, \\
то получим оптимальный поток размера $|f|+x$.
\end{Lm}
\begin{proof}
Обозначим $f^{*}$ оптимальный поток размера $|f|+x$, посмотрим на декомпозицию $f^{*} - f$, заметим, что все пути в ней имеют вес $\ge W(p)$, а циклы вес $\ge 0$.
\end{proof}

% Min Cost k-Flow в графе без отрицательных циклов
% Lm: mincost ⇔ не существует отрицательного цикла в остаточной сети
% Решение задачи min cost k-flow в графе без отрицательных циклов. Алгоритм: ищем произвольный путь min веса в остаточной сети алгоритмом Форда-Беллмана.
% Доказательство корректности: разность потоков.

\pagebreak
\vspace*{-1.5em}
\Subsection {Потенциалы и Дейкстра}

Для ускорения хотим Форда-Беллмана заменить на Дейкстру. \\
Для корректности Дейкстры нужна неотрицательность весов.\\
В прошлом семестре мы уже сталкивались с такой задачей, когда изучали \href{https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%BE%D0%BD%D1%81%D0%BE%D0%BD%D0%B0}{алгоритм Джонсона}.

\THE{Решение задачи mincost k-flow.}

Запустим один раз Форда-Беллмана из $s$, получим массив расстояний $d_v$, 
применим потенциалы $d_v$ к весам рёбер:

\vspace*{-1em}
\begin{smallformula}
$$e \colon a \to b \SO w_e \rightarrow w_e + d_a - d_b$$
\end{smallformula}

Напомним, что из корректности $d$ имеем $\forall e \ d_a + w_e \ge d_b \SO w^{'}_e \ge 0$.\\
Более того: для всех рёбер $e$ кратчайших путей из $s$ верно $d_a + w_e = d_b \SO w^{'}_e = 0$.

\down
В $G_f$ найдём Дейкстрой из $s$ кратчайший путь $p$ и расстояния $d'_v$. \\
Пустим по пути $p$ поток, получим новый поток $f^{'} = f + p$.\\
В сети $G^{'}_f$ могли появиться новые рёбра (обратные к $p$). Они могут быть отрицательными.\\
Пересчитаем веса:

\vspace*{-1em}
\begin{smallformula}
$$e \colon a \to b \SO w_e \rightarrow w_e + d'_a - d'_b$$
\end{smallformula}
Поскольку $d'$ -- расстояния, посчитанные в $G_f$, все рёбра из $G_f$ останутся неотрицательными.\\
$p$ -- кратчайший путь, все рёбра $p$ станут нулевыми $\SO$ рёбра обратные $p$ тоже будут нулевыми.

\THE{Псевдокод}

\begin{codep}
def applyPotentials(d):
	for e in Edges:
		e.w = e.w + d[e.a] - d[e.b]
d <-- FordBellman(s)
applyPotentials(d)
for i = 1..k:
	d, path <-- Dijkstra(s)
	for e in path: e.f += 1, e.rev.f -= 1
	applyPotentials(d)
\end{codep}

% Потенциалы и Дейкстра. Mincost k-flow за O(FordBellman + k×Dijkstra)

\Subsection {Графы с отрицательными циклами}

{\bf Задача:} найти mincost циркуляцию.

\down
{\bf Алгоритм Клейна:} пока в $G_f$ есть отрицательный цикл, пустим по нему $\min_e(c_e-f_e)$ потока.

\down
Пусть $\forall e \ c_e, w_e \in \Z \SO W(f)$ каждый раз уменьшается хотя бы на $1 \SO$  алгоритм конечен.

\down
{\bf Задача:} найти mincost $k$-flow циркуляцию в графе с отрицательными циклами.

\down
{\bf Решение \NO{1}:} найти за $|W(f)|$ итераций mincost циркуляцию, перейти от $f_0$ за $k$ итераций к $f_k$.

{\bf Решение \NO{2}:} найти любой поток $f \colon |f| = k$, в $G_f$ найти mincost циркуляцию, сложить с $f$.

\Subsection {Mincost flow}

{\bf Задача:} найти $f \colon W(f) = \min$, размер $f$ не важен.

Обозначим $f_k$ -- оптимальный поток размера $k$, $p_k$ кратчайший путь в $G_{f_k}$.

\begin{Lm}$W(p_k){\nearrow}$, как функция от $k$.\end{Lm}

\up\up
\begin{proof}
Аналогично доказательству леммы для Эдмондса-Карпа \autoref{lm@edmondskarp}.

От противного. Был поток $f$, мы увеличили его по кратчайшему пути $p$.\\
Расстояния в $G_f$ обозначим $d_0$, в $G_{f+p}$ -- $d_1$. \\
%Отрицательных циклов нет $\SO$ можем при подсчёте расстояний выбрать потенциалы: в $G_{f+p}$ все веса неотрицательны.
Возьмём $v \colon d_1[v] < d_0[v]$, а из таких ближайшую к $s$ в дереве кратчайших путей. \\
Рассмотрим кратчайший путь $q$ в $G_{f+p}$ из $s$ в $v$: $s \leadsto \dots \leadsto x \to v$.\\
$e = (v \to x), d_1[v] = d_1[x] + w_e, d_1[x] \ge d_0[x] \SO d_1[v] \ge d_0[x] + w_e \SO$ ребра $(x \to v)$ нет в $G_f \SO$\\
ребро $(v \to x) \in p \SO d_0[x] = d_0[v] + w_{\,\overline{e}} = d_0[v] - w_e \SO$\\
$d_1[v] = d_1[x] + w_e \ge d_0[x] + w_e = (d_0[v] - w_e) + w_e = d_0[v]$. Противоречие.
\end{proof}

\begin{Cons}
$(W(f_k) = \min) \EQ (W(p_{k-1}) \le 0 \wedge W(p_k) \ge 0)$.
\end{Cons}
Осталось найти такое $k$ бинпоиском или линейным поиском.
На текущий момент мы умеем искать $f_k$ или за $\O(k \cdot VE)$ с нуля, или за $\O(VE)$ из $f_{k-1}$ 
$\SO$ линейный поиск будет быстрее.

\Subsection {Полиномиальные решения}

Mincost flow мы можем бинпоиском свести к mincost k-flow.

Mincost k-flow мы можем поиском любого потока размера $k$ свести к mincost циркуляции.

Осталось научиться за полином искать mincost циркуляцию.

\THE{Решение \NO{1}:} модифицируем алгоритм Клейна, будем толкать $\min_e(c_e{-}f_e)$ потока по циклу $\min$ среднего веса.
Заметим, что ($\exists$ отрицательный цикл) $\EQ$ ($\min$ средний вес $< 0$).

\down
Решение работает за $\O(VE \log (nC))$ поисков цикла. Цикл ищется алгоритмом Карпа за $\O(VE)$.

Доказано будет на \href{http://acm.math.spbu.ru/~sk1/courses/1718f_au2/practice/171006.pdf}{практике}.

\THE{Решение \NO{2}:} Capacity Scaling.

Начнём с графа $c'_e \equiv 0$, в нём mincost циркуляция тривиальна.

Будем понемногу наращивать $c'_e$ и поддерживать mincost циркуляцию. В итоге хотим $c'_e \equiv c_e$.

%Алгоритм:

\begin{code}
for k = logU..0:
	for e in Edges:
		if c`\color{black}{$_e$ содержит бит $2^k$}`:
			c`\color{black}{$'_e$}` += `\color{black}{$2^k$}` // `\t{$e$: ребро из $a_e$ в $b_e$}`
			`\color{black}{Найдём $p$ -- кратчайший путь $a_e \to b_e$}`
			if `\color{black}{$W(p) + w_e \ge 0$}`:
				`\color{black}{нет отрицательных циклов $\SO$ циркуляция $f$ оптимальна}`
			else:
				`\color{black}{пустим $2^k$ потока по циклу $p + e$ (изменим $f$)}`
				`\color{black}{пересчитаем потенциалы, используя расстояния, найденные Дейкстрой}`
\end{code}
Время работы алгоритма $E \log U$ запусков Дейкстры $= E(E + V\log V)\log U$.

\begin{Lm}После $9$-й строки циркуляция $f$ снова минимальна.\end{Lm}
\begin{proof}
$f$ -- минимальная циркуляция до $4$-й строки, $f'$ -- после. \\
Как обычно, рассмотрим $f' - f$. Это тоже циркуляция. Декомпозируем её на единичные циклы. \\
Любой цикл проходит через $e$ (иначе $f$ не оптимальна). Через $e$ проходит не более $2^k$ циклов. \\
Каждый из этих циклов имеет вес не меньше веса $p+e \SO W(f') \ge W(f + 2^k(p+e))$.
\end{proof}

\up\up
\Subsection{\red{\t{(*)}} Cost Scaling}

% \TODO

\href{https://people.orie.cornell.edu/dpw/orie633/LectureNotes/lecture14.pdf}{Cost scaling (часть 1)}

\href{https://people.orie.cornell.edu/dpw/orie633/LectureNotes/lecture15.pdf}{Cost scaling (часть 2)}
