\Section{Минимальный глобальный разрез и Диниц} {12 апреля} {Привалихин Алексей}

\Subsection{Диниц с Link-cut tree}
  
\begin{MyList}
\item Как и в простом Динице, в начале каждой фазы строим слоистую сеть.
\item Как превратить нашу сеть в дерево? Запустим из стока DFS, который ходит только по ребрам, противоположные которым лежат в нашей слоистой сети. Ребра, противоположные тем, по которым он пройдет составляют дерево с корнем в истоке.
\item Создадим на этом дереве структуру Link-cut tree. Она должна будет хранить на путях минимум и его позицию(среди ребер), а также уметь вычитать из всех ребер пути одинаковую величину. Зачем: весом ребра будет разность пропускной способности ребра и потока по нему.
\item Возьмем минимум на пути из истока в сток (путь один, ибо дерево же!) и вычтем из всех ребер на этом пути. Хотя бы одно ребро обнулилось (причем точно обнулился тот минимум, позицию которого мы знаем из Link-cut tree). Сделаем cut по обнулившемуся ребру, а потом заменим его на другое (следующее в списке смежности соответствующей вершины, которое лежит в слоистой сети), сделав link его концов.
\end{MyList}
Таким образом, у нас есть $\O(V)$ фаз, на каждой из которых мы делаем DFS, а потом обнуляем не более $E$ ребер, за $\O(\log{V})$ каждое (ибо Link-cut со Splay-деревьями внутри). Таким образом, суммарная сложность -- $\O(V \cdot E \cdot \log{V})$.

Суть задачи -- удалить в неориентированном взвешенном графе множество ребер минимально возможного суммарного веса так, чтобы нарушить связность графа.\\
Примечание: в данной задаче будет использоваться термин "слить/соединить вершины". Это значит -- создать новую вершину, которая будет иметь все ребра обеих сливаемых (кратные сохраняются!) и убить две слитые.

\Subsection{Каргер-Штейн}

Примечание: в этом алгоритме мы считаем, что веса всех ребер равны 1 (иначе вероятность испортится). Однако, можно ребро веса k представить в виде k кратных ребер. Сложность испортится, но работать будет.\\
Примечание: Данный алгоритм -- вероятностный, а потому в оценке сложности будет присутствовать переменная C. Что это? Пусть у вас есть алгоритм, который имеет вероятность ошибки $\frac{1}{e}$. Пусть вы хотите, чтобы вероятность ошибки была $\frac{1}{C}$. Тогда вам всего лишь достаточно запустить ваш алгоритм $\log{C}$ раз и выбрать лучший из ответов.

\Subsubsection{$\O(n^4 \cdot \log{C}$)}

Основная идея данного алгоритма: в минимальном разрезе немного ребер. А точнее, если минимальная степень вершины равна k, то в минимальном разрезе не более k ребер (ибо просто отрезать вершниу с минимальной степенью -- тоже вариант). А всего в графе много ребер. А точнее, так как k -- минимальная степень, $E >= \frac{n \cdot k}{2}$.\\
Значит, если выбрать случайное ребро, то с вероятностью хотя бы $\frac{k \cdot 2}{n \cdot k} = \frac{2}{n}$ есть минимальный разрез, в котором этого ребра нет. Значит, можно слить концы этого ребра, ибо в ответе они будут по одну сторону разреза.\\
Делаем так, пока в графе больше двух вершин. В графе из двух вершин разрез единственный, он же минимальный. Вероятность ошибки -- $\prod\limits_{i = 3}^n{(1 - \frac{2}{i})} = \prod\limits_{i = 3}^n{(\frac{i - 2}{i})} = \frac{2}{(n - 1) \cdot n}$.\\ Не очень-то здорово. Но то, что мы делали до сих пор работало всего лишь за $\O(n^2)$. Поэтому, можно просто повторить алгоритм несколько раз и взять лучший из ответов. Если точнее, то повторим алгоритм $n^2$ раз. Тогда вероятность того, что все отработали неверно -- $(\frac{n^2 - 2}{n^2})^{n^2}$, что стремится к $\frac{1}{e^2}$ при n, стремящемся к бесконечности(причем, достаточно быстро). Применив то, о чем написано в примечании выше, получим нужные асимптотику и вероятность ошибки.\\
Примечание: можно сливать вершины не за линию, а быстрее, если использовать DSU.

\Subsubsection{$\O(n^2 \cdot \log^2{n} \cdot \log{C})$}

Вернемся к моменту, когда мы оценивали вероятность нахождения правильного ответа одним проходом алгоритма. $\prod\limits_{i = 3}^n{(\frac{i - 2}{i})}$ -- интересное произведение. Если точнее, то при достаточно больших i множители не сильно портят нашу вероятность, а при маленьких -- очень сильно. Тогда давайте разобъем произведение на две части: $\prod\limits_{i = \frac{n}{\sqrt{2}}}^n{(\frac{i - 2}{i})}$ и все остальное. Первая часть имеет вероятность ошибки $\frac{1}{2}$, а вторая... Со второй все похуже. Но можно запустить ее дважды (естественно, таким образом, чтобы разные ветки выбирали разные случайные ребра!). Вероятность корректного срабатывания (обозначу P(n)) теперь -- $\frac{1}{2} \cdot (1 - (1 - P(\frac{n}{\sqrt{2}}))^2)$. Неприятная штука. Но посчитать ее все же можно, если перейти в дифференциальные уравнения(не очень понятно, почему это так, но это так):\\
$f'(n) = -\frac{(f(n))^2}{2}$\\
$-\frac{f'(n)}{n^2} = \frac{1}{2}$\\ *Проинтегрировали обе части*\\
$\frac{1}{f(n)} = \frac{k}{2} + Const$\\
$f(n) = \frac{1}{\frac{k}{2} + Const}$ \\ *Подставим k = $\log_{\sqrt{2}}{n}$*\\
$f(n) = \frac{1}{\log{n}}$, где f(n) = P(n). Повторили $\log{n}$ раз и получили вероятность ошибки $\frac{1}{e}$ и сложность $\O(n^2 \cdot \log^2{n})$, а получать отсюда требуемые сложность и вероятность ошибки мы уже умеем.

\Subsection{Штор-Вагнер}

Этот алгоритм состоит из множества фаз. До первой фазы считаем, что ответ -- бесконечность. На каждой фазе мы:
\begin{MyList}
\item Берем произвольную вершину(например, первую) и добавляем ее в множество(в начале фазы множество пустое).
\item Начинаем добавлять в множество остальные вершины, причем каждый раз добавляется самая "связанная" с этим множеством вершина, еще не лежащая в нем.
\item Добавив таким образом все вершины в наше множество, посмотрим на последние две. Утверждается(у нас без доказательства, но на emaxx-е оно есть), что минимальный глобальный разрез, который разделяет их -- это тот, который попросту отрезает последнюю вершину от всех остальных. Значит, либо такой разрез -- это ответ, либо эти две вершины в ответе будут лежать по одну сторону разреза. А тогда их можно объединить в одну вершину.
\item Значит, в конце фазы надо сделать две вещи: обновить ответ (минимум из текущего ответа и разреза, отрезавшего последнюю вершину от остальных) и слить две последние вершины в одну.
\item Конец фазы. Повторять, пока не останется 2 вершины. Для них разрез очевиден. Обновим ответ в последний раз и выведем его.
\end{MyList}
Сложность алгоритма -- $\O(n^3)$, если искать самую связанную вершину за линию, или $\O(n \cdot (m + n \cdot \log{n}))$, если не полениться и написать кучу Фибоначчи. 
