\Section{Сложные потоки}{8 апреля}{Даниил Смирнов}

\Subsection{Вспомнить все} \\
    \Subsubsection{Разность потоков одинакового размера}
        \begin{Lm} 
            $\forall f_1, f_2: |f_1| = |f_2|$ \\
            $f_2 - f_1$ --- циркуляция $G_{f_1}$ \\
            Доказательство: $f_2 - f_1 \leqslant c - f_1$
        \end{Lm}

    \Subsubsection{Эдмондс-Карп}
        \begin{MyList}
            \item BFS --- кратчайший путь из истока в сток
            \item Пускаем поток, равный минимальной остаточной пропускной 
                способности на этом пути
            Time = $VE \cdot BFS = VE ^ 2$
        \end{MyList}
        \begin{Lm} 
            $d[s \rightarrow t] \nearrow$ в $G_f$ \\
            Посмотреть, где угодно, или вспомнить прошлую лекцию.
        \end{Lm}
        \begin{Lm} 
            Всего будет не более $\frac{VE}{2}$ запусков. \\
            Доказательство: $\forall$ --- ребро насытится $\frac{V}{2}$ раз 
                (так как d[e] строго увеличивается, а расстояние не превысит 
                $V$; при этом, чтобы насытить, надо ``насытить'' в обратную 
                сторону)
        \end{Lm}

\Subsection{Масштабирование потока} \\
    $E \log U \cdot ``path finding'' = E ^ 2 \log U$, где $U$ --- максимальная 
    пропускная способность
    \begin{lstlisting}[language=c++,gobble=8]
        for (int k = 2 ^ t; k > 0; k >>= 1) { // U >= 2 ^ t > U / 2
            while (Exists such path) {
                Find path with c_e - f_e >= k;
                Push flow of size k;
            }
        }
    \end{lstlisting}
    \begin{Lm}
        На каждом шаге не более $2E$ путей \\
        Доказательство: рассмотрим переход от $2k$ к $k$. Мы уже не можем 
            протолкнуть поток размера $2k$. Таким образом, задается разрез. 
            Значит, его пропускная способность $\leqslant 2k \cdot E$. Значит, 
            в нем мы протолкнем $\leqslant 2E$ раз поток размера $k$
    \end{Lm}

\Subsection{Алгоритм Диница} \\
    $VE \cdot V$ (работаем, как Эдмондс-Карп, но ищем путь быстро): \\
    Рассмотрим граф после работы $BFS$. Он делится на слои по расстоянию от 
    истока. Построим новый граф. В нем останутся только те ребра, которые ведут
    из слоя в следующий. Теперь модифицированным $dfs$-ом ищем в новом графе 
    пути длины $d$, где $d$ --- кратчайшее расстояние в остаточной сети. $dfs$ 
    при откате назад удаляет ребро, по которому возвращается.
    \begin{lstlisting}[language=c++,gobble=8]
        for (;;) {
            d = bfs(s, t);
            while (Exists path of len d) {
                Find path;
                Push flow;
            }
        }
    \end{lstlisting}
    Оценим время: пусть $K_d$ --- число путей длины d. Тогда для каждого $d$ мы
    сделаем $E + d \cdot K_d$ операций. Сложим все. $\sum_{d}(E + d \cdot K_d) 
    \leqslant VE + V \cdot \sum_{d} K_d \leqslant VE + V \cdot \frac{VE}{2} = 
    \O(V ^ 2 E)$ \\
    \Subsubsection{+Scaling}
        \begin{lstlisting}[language=c++,gobble=8]
            for (k = 2 ^ t; k; k >>= 1) {
                Dinic(k);
            }
        \end{lstlisting}
        \begin{Thm}
            $VE \log U$ \\
            Доказательство: посмотрим оценку $VE + V \cdot \sum_{d} K_d$. Где
                $\sum_{d} K_d \leqslant 2E$ из доказательства масштабирования
        \end{Thm}

\Subsection{Хопкрофт-Карп} \\
    Ищем паросочетание Диницом
    \begin{Thm}
        $\O(E \sqrt V)$ \\
        Доказательство: \begin{MyList}
            \item Фаза = $\O(E)$
            \item После первых $\sqrt V$ фаз $d(s, t) > \sqrt V$
            \item Рассмотрим симметрическую разность полученного сочетания и 
                максимального. Все разбилось на пути. Так как они не 
                пересекаются, а длина их $> \sqrt V$, то всего их $\leqslant 
                \sqrt V$. Тогда осталось достроить не больше корня. То есть 
                всего $\leqslant 2 \sqrt V$ фаз
        \end{MyList}
    \end{Thm}
    Замечания:
    \begin{MyList}
        \item Надо писать, как Куна (сразу обратно по взятому ребру прыгать).
        \item Из структуры графа пересечение по вершине влечет за собой 
            пересечение по ребру, поэтому достаточно помечать вершины и не 
            ходить в них.
    \end{MyList}
