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

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

[L,R] Потоки

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

Паросочетания

  1. Матрица Татта, det = многочлен
  2. Теорема Татта: det тождественно равен нулю тогда и только тогда, когда не существует совершенного паросочетания
  3. Рандомизированный алгоритм проверки совершенности
  4. Алгоритм построения макс паросочетания в произвольном графе

Задачи

  1. [matching] Задачка про такси, сведение к паросочетанию.
  2. [matching] Задача с РОИ: каждый пассажир = отрезок дней [ai, bi], в каждый день может улететь K пассажиров
  3. [cover] Замощение грида минимальным числом палок 1xN
  4. [cover] Удаление графа
  5. [flow] Округление вещественной матрицы округленными числами с сохранением суммы в строках и столбцах
  6. [independent set] party
  7. [max clique] birthday
  8. Not read [cut] Задача про заказы и инструменты
  9. [mincost-flow] Нужно последовательность разбить на K подпоследовательностей: разница индексов не более X, разница значений не более Y.

Задачи (2-я серия)

  1. Дан произвольный двудольный граф, нужно разбить его на минимальное кол-во паросочетаний.
  2. Покрытие ацикличного графа цепями
  3. Максимальная антицепь (двойственность с покрытием)

Про математику

  1. Поиск обратного к x mod 2n за O(logn)

Memory Managment и Garbage Collection

  1. Not read gc: ссылки
  2. Not read gc: список всего, и offline обход от существующих корней
  3. mm: рекурсивная функция и стэк
  4. mm: объекты одинакового размера и список
  5. mm: real life - многие объекты имеют одинаковый размер
  6. mm: list of objects [2k..2k+1), линейное время
  7. mm: дефрагментация
  8. mm: выделение самого малого куска соответствующего размера от начала, склейка свободных при освобождении