\Section{Венгерский алгоритм}{25 марта}{Никита Сазанович}

\Subsection{Задача и способы ее решения}

Известна под названием ``Задача о назначениях''.
Дана матрица весов $w[i, j]$ -- стоимость выполнения j-ой работы i-ым работником. Необходимо каждому рабочему назначить работу и минимизировать суммарную стоимость выполнения.

Способы решения: 
\begin{MyList}
\item MinCostFlow за $\O(V^3)$ или $\O(VE \log C)$.
\item Венгерский алгоритм за $\O(V^3)$. Преимуществом этого решения является маленькая константа.
\item Линейное программирование. Работает за $\O(V^3)$, хотя сам алгоритм экспоненциальный. Можно обобщить для произвольного графа. 

Заключается же он в назначении значений $0 \le x[i, j] \le 1$ при выполнении условий $ \forall i \sum\limits_{j=1}^{n}x[i, j]=1$ и $\forall j \sum\limits_{i=1}^{n}x[i, j] = 1$, минимизирую при этом $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}x[i,j]w[i,j]$. С этим помогает справится simplex method. Можно доказать, что значения $x[i, j]$, найденные этим алгоритмом, будут целыми.
\end{MyList}

\Subsection{Идея венегерского алгоритма}

Заметим, что прибавив константу к столбцу либо строке, мы изменим ответ на эту же константу. Тогда сделаем все значения в матрице неотрицательными, т.е. отнимем от каждой строки ее минимум и получим $w[i,j] \ge 0$. Теперь, поддерживая это свойство и всегда добаваляя к паросочетанию ребра с весом 0, мы построим оптимальный ответ. 

Осознав это, построим алгоритм:
\begin{MyList}
\item Будем каждую вершину добавлять к паросочетанию, как-то изменяя текущее паросочетание. Поддерживаем четыре множества: $A^{+}$ -- вершины первой доли, в которых мы уже были в dfs; $A^{-}$ -- в которых еще не были; аналогично определим для вершин второй доли $B^{+}$ и $B^{-}$.

\item Сразу заметим, что ребра текущего паросочетания выглядят как вершина из $A^{+}$ и $B^{+}$, либо из $A^{-}$ и $B^{-}$. Тогда понятно, что хорошо бы рассмотреть в качестве кандидата на добавление нулевое ребро из $A^{+}$ и $B^{-}$, ведь, оказавшись бы та вершина незанятой, мы увеличили бы паросочетание, не нарушив при это вышеизложенных правил. 

\item Теперь нам нужен такой 0. Для этого проделаем следующий ``фокус'': найдем минимальный элемент в подматрице $A^{+}\times B^{-}$, обозначим его $m$; вычтем  $m$ из всех строк $A^{+}$ и добавим $m$ ко всем столбцам $B^{-}$. Вычитаем, чтобы получить 0, а добавляем для того, чтобы не получить элементы меньшие нуля в подматрице $A^{+}\times B^{+}$.

\item В итоге получили 0. Если вершина из $B^{-}$ свободна(а она могла быть занята текущим паросочетанием), то мы нашли увеличение. Иначе повторим шаг 3, изменив при этом поддерживаемые множества(одна вершина покинула $A-$ и появилась в $A+$, то же с вершиной из $B-$).
\end{MyList}

\Subsection{Псевдокод алгоритма}

\begin{code}
for (int i = 0; i < n; i++) {
	A_plus = v, B_minus = all_from_B;
	while (true) { \\ takes O(V) time
		m = min in A_plus x B_minus; \\ `$\O(V^2)$`
		change matrix;  \\ O(V^2)
		find 0 in A_plus x B_minus; \\ `$\O(V^2)$`
		if vertex free {
		    update_route;
		    break;
		}
	}
}
\end{code}

Видно, что алгоритм работает за $\O(V^4)$.

\Subsection{Оптимизация до $\O(V^3)$}

Хочется сделать внутреннюю часть за $\O(V)$.
Введем потенциалы для весов ребер: истинный вес = \t{w[i,j] + row[i] + column[j]}.
Уже умеем делать ``фокус'' за линейное время. Осталось лишь совершать две операции за линия. 
Здесь нам поможет аналогия с алгоритмом Прима. 
В нем поддерживается минимальный вес ребра, которое ведет в вершину -- мы сделаем то же самое. 
Тогда отвечать на эти запросы мы сможем проходя весь массив минимумов за линию.