Решение задач суф. массивом и суф. деревом

  1. Наибольшая общая подстрока
  2. Найти k-ю лексикографически подстроку
  3. Найти подстроку S за O(|S|) в суф.дереве и O(|S|*log|Text|) в суф.массиве (с учетом предподсчета)
  4. Найти количество подпалиндромов строки
  5. Найти минимальный циклический сдвиг строки

Решение задач Ахо-Корасиком

  1. Для каждого слова словаря определить, сколько раз встречается это слово.
  2. Слова удаляются, добавляются, нужно поддерживать возможность быстро по тексту узнать, встречаются ли в нем словарные слова.

Потоки. Введение.

  1. 2 неперсекающихся по ребрам пути - поток. k неперсекающихся по ребрам пути - поток.
  2. Определение потока (f) в общем случае. 0 <= f <= c. Сумма f для каждой вершины = 0. f[e] = -f[e']
  3. Решение задачи о k неперсекающихся по ребрам пути. Картинка, почему "просто k раз пустить dfs" не работает.
  4. Непересекающиеся по вершинам пути. Раздвоение вершин.
  5. Разрез C(A,B) - разрез между множествами. C(s,t) - разрез между вершинами. |C(s,t)| >= |f(s,t)|.
  6. Теорема и алгоритм Форда-Фалкерсона. Если нет дополняющего пути, |C(s,t)| = |f(s,t)|. Алгоритм ищет и поток, и разрез за O(|f|*E)
  7. Нахождение паросочетания в двудольном графе с помощью потока за O(VE).

Потоки. Алгоритмы поиска.

  1. Пускаем каждый раз максимум по пути
  2. Алгоритм Эдмондса-Карпа за O(VE2) (пускаем bfs)
  3. Масштабирование за O(E2logMax) (пускаем не менее 2k)
  4. 1 + 3 = O(E2)

Разрезы

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

MinCost Потоки.

  1. Задача: ищем поток размера k минимального веса. Обратное ребро имеет вес (-w).
  2. Формулировки прикладных задач: Задача о назначениях. Транспортная задача.
  3. Алгоитм поиска: База = нет отрицательных циклов, переход = добавляем инимальный путь.
  4. Док-во корректности: рассмотрим разность mincost потока размера (k+1) и mincost потока размера (k).

Потоки. Обобщение.

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

Задачи на потоки

  1. [matching] Покрытие грида с дырками доминошками
  2. [flow] Футбольный турнир от Пети Митричева
  3. [flow] Восстановление матрицы по суммам в сторках и столбцах
  4. [mincost-flow] Теория расписаний: K автоматов, выполнить i-заказ = занять один из автоматов в отрезок [Li..Ri]. Каждый автомат в каждый момент времени выполняет одно задание.