
\Section{Mincost flow}{3 мая 2016г. }{Плющ}
	
	Есть граф. У каждого ребра есть пропускная способность, величина потока, через него протекающего и вес ($c_e, f_e, w_e$). Числа вещественные.
	
	Ищем поток. Весом потока f является $w(f)\frac{1}{2}\sum\limits_{e \in f}f_ew_e$. Cуммирование по прямым и по обратным рёбрам. Полусумма из-за того, что если есть ребро ($f_e, w_e$), то обратным ребром (которое мы сами сделаем) будет ($-f_e, -w_e$).

	\Subsection{4(четыре) задачи}
		\begin{enumerate}
			\item Mincost k-flow: (|f| = k) AND (w(f) $\to$ min)
			\item Mincost flow: (w(f) $\to$ min)
			\item Mincost circulation: Mincost 0-flow
			\item Mincost maxflow: Mincost k-flow, |f| $\to$ max
		\end{enumerate}
					
	Видим, что задачи очень похожи. Например, 1-ая(первая) задача к 3-ей(третьей) сводится добавлением ребра из стока в исток с пропускной способностью k и бесконечно большим отрицательным весом.

	\Subsection{Алгоритм Клейна для mincost circulation}

		Пока есть цикл отрицательного веса, пустим по нему $\min\limits_{e \in negcycle}(c_e - f_e)$.
		
		Отметим, что при целых параметрах рёбер алгоритм конечный, просто потому что 
		
		$Time \leq |w(f)|\cdot O(finding\_negcycle)$  			
	\begin{Lm}
		Среди всех потоков заданного размера поток f имеет минимальный вес $\Longleftrightarrow$ в $G_f$ нет negcycle.
	\end{Lm}
	\begin{proof}
		\begin{enumerate}
			\item[$\Rightarrow$] Если неверно, то пустим поток по negcycle, т.е. уменьшим w(f).
			\item[$\Leftarrow$] $G_f = f_1 - f$ = mincost - answer\_we\_have. Это циркуляция, т.е. набор циклов, причём неотрицательных. Поэтому $w(f_1) \geq w(f)$. Но $f_1$ - mincost.
		\end{enumerate}
	\end{proof}
	
	\Subsection{Алгоритм через доп.пути}
		
		Пусть есть $f_k$ - ответ для mincost k-flow.

		$f_{k + 1}$ = $f_k + min\_path(G_{f_k})$
	\begin{proof}
		Расмотрим разность $f_{k + 1}$ и $f_k$ в $G_f$. Это путь и циркуляция, вес которой неотрицательный (лемма), значит, вес разности не меньше веса пути, который не меньше веса кратчайшего пути.
	\end{proof}		
	
	Если нет отрицательных циклов. то $f_0$ = 0, а если есть, то сделайте, чтоб не было.
	
	Mincost flow можно искать так же, только остановиться надо, когда вес пути стал неотрицательным (можно бинпоиском такое поискать, если хочется).
