Потоки. Крутые алгоритмы поиска.

1. Диница за O(V²E)
2. Диница + масштабирование за O(VElogMax)
3. Хопкрофт-Карп за O(EsqrtV)

Потоки. Доказательства.

1. Лемма: после bfs-а длины путей только увеличиваются.
2. Эдмондс: каждый раз одно ребро насыщается, каждое ребро рассыщается не более V/2 раз
3. Масштабирование: на каждой из log фаз есть разрез, через него проходят не более E путей
4. Диница: время работы dfs = V + удаление ребер, поэтому фаза за VE
5. Диница + масштабирование: сумма всех (dfs = V + удаление ребер) = VE + VE.

MinCost Потоки.

1. Потенциалы и Дейкстра.
2. Нахождение паросочетания миимального веса в двудольном графе с помощью mincost потока за O(V³).

[L,R] Потоки

1. Потоки с избытками и недостатки в вершинах, сток и исток отсутствуют
2. Потоки с избытками и недостатки в вершинах, некоторые вершины могут быть стоками и истоками.
3. [L,R] потоки.
1. Решение за O(MinCostFlow).
2. Решение за O(Flow): Ребро [L,R] заменяем на ребро [0,R-L] и избыток и недостаток в концых ребра.

Циркуляции

1. Циркуляция мин веса
2. [L,R] циркуляция

Разрезы

1. (s,t) разрез ищется потоком
2. Разрез минимальной стоимости: Summ(w[e]), Summ(w[e]*c[e]) ищутся так же. Т.е. можно для любой f(e) >= 0 минимизировать сумму по разрезу f(e).
3. Глобальный разрез. Наивное построение за O(N*Flow)

Про раскраску графов

1. Вершины можно раскрасить в maxDeg+1 цвет
2. Теорема Визинга (без. док-ва) ребра можно раскрасить в maxDeg+1 цвет (а нужно как минимум maxDeg, так что оценка почти точна).
3. 2 приближенных алгоритма раскраски вершин графа в K цветов

Задачи

1. [flow] Округление вещественной матрицы округленными числами с сохранением суммы в строках и столбцах