\Section{Цикл отрицательного веса и цикл минимального среднего веса.}{23 ноября}{Привалихин Алексей}

\Subsection{Цикл отрицательного веса.}
Добавим в граф фиктивную вершину, и направим из нее (но не в нее!) ребра нулевого веса во все остальные. Запустим из нее алгоритм Форда-Беллмана.\\
Как известно, за первую $n - 1$ итерацию алгоритм Форда-Беллмана находит все кратчайшие пути, состоящие из не более чем $n - 1$ ребер.
Значит, если на $n$-ной итерации произошла релаксация, то в графе есть кратчайший путь длины $n$, а в пути длины $n$ обязательно есть цикл.
Так как этот путь кратчайший (причем цикл веса $0$ не релаксируется алгоритмом Форда-Беллмана), то этот цикл имеет отрицательный вес 
(иначе без него путь бы стал короче).\\
Восстановление ответа: достаточно для каждой вершины хранить последнюю вершину на пути в нее.
Когда найдена вершина, расстояние до которой улучшилось на n-ной итерации, достаточно идти из нее назад, пока не будет найден цикл.\\
Осталось доказать, что если в графе есть цикл отрицательного веса $v_0, v_1, \dots, v_k$, где $v_0 = v_k$,
то Форд-Беллман сделает хотя бы одну релаксацию на $n$-ном шаге.
Предположим, что этого не произошло. Тогда после $n - 1$ релаксации для всех $i$ от $1$ до $k$ $d[v_i] \le d[v_{i - 1}] + w(v_{i - 1}, v_i)$.
Если просуммировать это неравенство по всем $i$ от $1$ до $k$, получится, что
$\sum \limits_{i = 0}^{k - 1}{d[v_i]} \le \sum \limits_{i = 1}^{k}{d[v_i]} + \sum \limits_{i = 1}^{k}{w(v_{i - 1}, v_i)}$,
а так как $v_0 = v_k$, это равносильно $0 \le \sum \limits_{i = 1}^{k}{w(v_{i - 1}, v_i)}$, то есть тому, что наш отрицательный цикл неотрицателен.\\
Сложность алгоритма равна сложности алгоритма Форде-Беллмана и равна $\O(VE)$.\\
Примечание: такой алгоритм находит только отрицательные циклы, достижимые из стартовой вершины алгоритма.
Чтобы алгоритм работал корректно, нужно добавить фиктивную вершину, из которой провести ребра во все остальные (но не обратно!), и запускаться из нее.

\Subsection{Цикл минимального среднего веса.}

\Subsubsection{Бинпоиск.}
Воспользовавшись умением находить отрицательный цикл за $\O(VE)$, можно сделать следующее:
перебрать бинпоиском минимальный средний вес (очевидно, он не меньше минимального веса ребра графа и не больше максимального).
Для каждого значения минимального среднего веса вычтем за $\O(E)$ из весов всех ребер выбранное значение, а затем проверим, есть ли в графе отрицательный цикл.
Сложность -- $\O(VE\log{M})$, где $M$ -- разность максимального и минимального весов ребер в графе.

\Subsubsection{Алгоритм Карпа.}
Итак, задача: избавиться от логарифма. Для этого разобъем задачу на 2 части:
нахождение минимального среднего веса цикла и нахождение самого этого цикла при известном минимальном среднем весе.\\
Вторая часть уже разобрана в предыдущем методе (вычитание найденного значения + $\EPS$ из весов всех ребер и поиск цикла отрицательного веса).\\
Теперь, собственно, нахождение минимального среднего веса цикла в графе. Определю $d[k,v]$ как длину кратчайшего пути из вершины $s$ в $v$ по $k$ ребрам
(считается Фордом-Беллманом). Теперь определю $\mu$ как $\min \limits_{v}(\max \limits_{k = 0}^{n - 1}(\frac{d[n, v] - d[k, v]}{n - k}))$.
Докажу, что это и есть искомый ответ. Для этого достаточно сказать, что:\\
\begin{enumerate}
  \item При увеличении (уменьшении) весов всех ребер на одну и ту же константу, ни $\mu$, ни ответ (обозначу его как $X$), не изменятся по определениям.
  \item Если доказать, что при $X = 0 \cdot \mu = 0$, то при любом $X \mu = X$ (следует из предыдущего пункта).
  \item Заметим, что при $X = 0$ граф без отрицательных циклов. Для него $\mu$ по определению неотрицательна, так как знаменатель 
    $(\frac{d[n, v] - d[k, v]}{n - k}$ всегда положителен, а числитель $\max \limits_{k = 0}^{n - 1}(\frac{d[n, v] - d[k, v]}{n - k}) = 0$
    равен разности кратчайшего пути из n вершин и кратчайшего пути вообще, что является неотрицательной величиной.
  \item При $X = 0$ существует вершина v, для которой $\max \limits_{k = 0}^{n - 1}(\frac{d[n, v] - d[k, v]}{n - k}) = 0$.
    Так как $X = 0$, в графе существует $0$-цикл. Возьмем некоторую вершину $u$ на этом цикле.
    Пусть кратчайший путь до нее состоит из $k$ ребер. тогда пойдем из этой вершины далее по нулевому циклу $n - k$ раз,
    пока не прийдем в некоторую вершину $v$. Обозначу сумму весов на пути по нулевому циклу из $u$ в $v$ как $А$, а из $v$ в $u$ как $В$.
    По определению $А + В = 0$. С одной стороны $d[v]$ (кратчайший путь до вершины $v$) не больше $d[u] + A$.
    С другой стороны, если предположить, что $d[v] < d[n, v]$, при том что $d[n, v] \le d[u] + A$, получаем:
    $d[u] \le d[v] + B < d[u] + A + B = d[u]$, что ложно.
    Значит, $d[v] = d[n, v]$, что значит, что $\max \limits_{k = 0}^{n - 1}(\frac{d[n, v] - d[k, v]}{n - k}) = 0$,
    а так как $\mu$ неотрицательна, $\mu = 0$.
\end{enumerate}
Из написанного выше видно, что $X = \mu$. Восстановление такое же, как и в алгоритме с бинпоиском. Сложность -- $\O(VE)$.\\
Примечание: также как и в алгоритме с бинпоиском, надо добавить фиктивную вершину. Также, в этой задаче считалось, что если нет пути из $s$ в $v$ по $k$ ребрам,
$d[k, v] = \infty$. Также, $\infty - \infty = \infty$. Таким образом, если в графе нет циклов, то $d[n, v] = \infty$, то есть $\mu = \infty$.
