	\Section{Алгоритм Гольдберга}{27 ноября}{Зуев Михаил}
		\Subsection{Алгоритм Гольдберга}
	
	{\bf Задача:} В графе без отрицательных циклов найти такой потенциал $p: V \rightarrow\mathbb{R}$, что $\forall e(a, b) \in E: w'_e = w_e + p(a) - p(b) \geq 0$.\\
	
	Пусть в графе веса всех ребер ограничены снизу. Т.е. $\forall e \in E: w_e \in \mathbb{Z}~\cap [-N; +\infty]$ для некоторого $N > 0$. Тогда алгоритм Гольдберга может решить данную задачу за время  $O(E\sqrt{V}\log N)$.\\ 
	
	Научимся решать задачу для случая $N = 1$. Все ребра графа разбиваются на 3 класса:\\
	
$		
		w_e =
		\begin{cases}
		-1\\
		0\\
		x, & x > 0
		\end{cases}
$\\

	{\bf Решение за $O(EV)$.}\\
	\begin{Def}
		Назовем вершину плохой, если в нее входит ребро веса -1.
	\end{Def}
	\begin{Def}
		Ребро $e(a, b)$называется исходящим ребром множества вершин $A$,если $a\in A, b \notin A$.
	\end{Def}
	\begin{Def}
		Ребро $e(a, b)$ называется входящим ребром множества вершин $A$, если $a\notin A, b \in~A$.
	\end{Def}
	\begin{Def}
		Ребро $e(a, b)$ называет внутренним ребром множества вершин $A$, если $a\in A, b \in A$.
	\end{Def}
	\begin{Def}
		Ребро $e(a, b)$ называет внешним ребром множества вершин $A$, если $a\notin A, b \notin A$.
	\end{Def}
	
	Алгоритм будет итеративым. Каждая итерация состоит из 5 шагов:
	\begin{enumerate}
		\item 
			Находим плохую вершину $v$. Пусть $e(x, v): w_e = -1$.
		\item
			Запускаем dfs из $v$ по ребрам с весами -1 и 0. Все посешенные вершны образуют множество $A\subset V$. Если $x \in A$, то существует неположительный путь из $v$ в $x$, а значит есть и отрицательный цикл (т.е. у нас уже есть отрицательное ребро из $x$ в $v$).
		\item
			Для всех $a \in A$ делаем $p(a) -= 1$. При этом $w'_e$ внутренних ребер $A$ не изменился (+1 с одного конца и -1 с другого), входящих увеличился на 1, а исходящих уменьшился на 1. Но т.к. все исходящие ребра имеют положительный вес (иначе мы прошли бы по этому ребру в dfs-е), то все исходящие ребра остались неотрицательными.
		\item
			Вершина $v$ перестала быть плохой. Новых плохих вершин не образовалось, т.к. не появилось новых отрицательных ребер.
		\item 
			Если в графе не осталось плохих вершин, то заканчиваем~-- у нас не осталось отрицательных ребер.
	\end{enumerate}
	В худшем случаи мы сделаем $V$ итераций, на каждой $dfs$ отработает за $O(V + E)$. Получаем время работы $O(VE)$.\\
	\newpage
	{\bf Решение за $O(E\sqrt{V}))$.}\\
	\begin{Lm}
		Если из некоторого множества $A$ пошагово удалять $\geq \sqrt{|A|}$ элементов ($|A|$~-- размер множества на текущем шаге), то множество станет пустым через $O(\sqrt{|A_0|})$ шагов ($|A_0|$~-- изначальный размер).
	\end{Lm}
	\begin{proof}
		Представим размер множества как клетчатый прямогульник со сторонами примерно $\sqrt{|A_0|}$. Тогда каждый шаг удаления можно соотнести с отрезанием от прямоугольника строки/столбца (чередуются). Кол-во строк и столбцов в этом прямоугольнике $O(\sqrt{|A_0|})$. После удаления всех строк и слобцов наше множество станет пустым. 
	\end{proof}
	Алгоритм будет итеративым. Каждая итерация состоит из n шагов:
	\begin{enumerate}
		\item
			Сконденсируем граф по -1-м и 0-м ребрам. Если внутри какой-то компоненты оказалось ребро веса -1, то мы нашли отрицательный цикл внутри этой компоненты.
		\item
			Добавим фиктивную вершину $S$ и проведем из нее ребра веса 0 во все другие вершины.
		\item
			Найдем расстояние от вершины $S$ до всех других по -1, 0 ребрам. Т.к. в графе нет циклов, то это можно сделать с помощью динамики за $O(E)$.
		\item
			Разобьем все вершины на слои в зависимости от посчитанного расстояния. Если вершина $v$ лежит в $i-$м слое, то существует путь из $S$ в $v$, в котором будет $i$ ребра веса -1. Обозначим за $k$ кол-во оставшихся плохих вершин. Тогда, по принципу Дирихле, есть или слой, в котором $\geq \sqrt {k}$ плохих вершин, или кол-во слоев $\geq \sqrt {k}$ (не считая 0-го, т.к. в нем нет плохих вершин).
		\item
			Рассмотрим 2 случая:
		\begin{enumerate}
			\item
				Есть слой, в котором $\geq \sqrt {k}$ плохих вершин. Тогда, запустим dfs из всех этих вершин аналогично 1-му решению, образуем множество $A$. Заметим, что вершины более ранних слоев не могут лежать в этом множестве. Применим $p(v) -= 1$ для всех вершин множества. Все исходящие ребра мы не испортим. Т.к. все ребра веса -1, которые входили в плохие вершины, шли из более раннего слоя, то после изменения потенциала их вес станет равен 0. Т.е. все плохие вершины из этого слоя хорошими, а новых не образовалось.
			\item
				Кол-во слоев $\geq \sqrt {k}$. Тогда, по сказанному в 4 пункте, есть простой путь, в котором $m \geq \sqrt {k}$ ребер веса -1, значит и $m \geq \sqrt {k}$ плохих вершин.\\
				Рассмотрим этот путь. Пронумеруем плохие вершины этого пути с конца (т.е. путь будет идти в порядке $v_m, v_{m - 1}, \dots , v_2, v_1$).\\
				Запустим dfs из $v_1$, получим множество $A_1$. Для всех вершин пометим, что они были добавлены в 1 множество. Теперь мы должны были бы запустить dfs из $v_2$ и получить множество $A_2$. Но это долго. Заметим, что $A_1 \subset A_2$ (т.к. $v_1$ достижим из $v_2$). Множество $A_2$ состоит из 3-х частей: вершин, которые достижимы из $v_2$, то не достижими из $v_1$; вершины, которые лежат в $A_1$; вершины, которые достижимы из $v_1$, но в момент запуска dfs из $v_1$ в них вели положительные ребра (при применении $p(v) -= 1$ к $A_1$ веса исходящих ребер уменьшились и могли стать 0). Чтобы обработать 1-ю группу просто запустим dfs из $v_2$, ходить будем только по непосещенным вершинам. Чтобы обрабатывать 3-ю группу, заведем магическую структуру $Vector$, которая по номеру плохой вершины возвращает список ребер, которые могли "обнулиться" при обработке предидущей плохой вершины.\\
				Получаем следующий порядок действий: при обработке $v_i$ запускаем dfs по еще не посещенным вершинам, а также из концов ребер, которые могли обнулиться на текущем шаге (если вершина на другом конце ребра уже лежит в каком-то множестве или ребро не обнулилось, то ничего не делаем); помечаем посещенные вершины, что они принадлежат $i$-му множеству; добавляем в структуру новые исходящие ребра-кандидаты.\\
				Заметим, что после $i$-го запуска мы сделали вершину $v_i$ хорошей. Т.е. мы сделалем все $m$ вершин хорошими.\\
				Само значение потенциала для вершин можно изменять не на каждом шаге, а в конце, по номеру множества, в которое его добавили (это будет 1-е попадание, на последующих шагах мы всегда делали $-=1$ для этой вершины).
		\end{enumerate}
	\end{enumerate}
	
	Опишем структуру $Vector$. Это будет вектор векторов размера $E$. Ребро веса $a$, которое добавили на шаге $b$, кладем в список $a + b$. При обработке $i$-й плохой вершины мы смотрим в $i$ список. Для ребер этого списка верно, что с момента их добавления прошло $a$ (вес ребра) шагов, а значит мы могли $a$ раз уменьшить его вес на 1. Ребра веса больше $E$ можно игнорировать (т.к. оно не успеет стать нулевым).\\
	
	На каждой интерации мы делали хорошими  $\geq \sqrt {k}$ плохих вершин, а значит мы сделаем $O(\sqrt{k})$ итераций, что в худшем случаи $O(\sqrt{V})$. На каждой итерации мы совершали $O(V + E)$ операций, а значит время работы $O(E\sqrt{V})$.\\
	
	{\bf Обобщение решения.} Покажем, как использовать полученное решение для любого $N$.\\
	Пусть $N = 2d + 1$. Будем использовать решение для $N = 1$, чтобы перейти к $N = d$. Для этого запустим его с учетом следующих переобозначений:\\
	
	\begin{tabular}{|c|l|l|}
	\hline
		$w_e \in [-(2d+1);-(d + 1)]$ & -1\\
	\hline
		$w_e \in [-d;0]$ & 0\\ 
	\hline
		$w_e > 0$ & $\lceil\frac{w_e}{d + 1}\rceil$ (вес при добавлении в структуру)\\
	\hline
		$p(v) -= (d + 1)$ & $p(v) -= 1$\\
	\hline
	\end{tabular}\\


	Исходный алгоритм для всех ребер веса -1 ставил вес $\geq 0$. Теперь алгоритм для всех ребер из $[-(2d+1);-(d + 1)]$ сделает вес $\geq d$. Таким образом, за $\log N$ применений этого алгорима все ребра будут иметь вес $\geq 0$.\\
	Получаем время работы $O(E\sqrt{t}\log N)$.
