Графы, жадность (27 ноября 2013)

  1. Бинарный поиск по ответу
    1. Выбрать k объектов из n так, чтобы... (дробь → min)
    2. Цикл минимального среднего веса за O(VElogM)
    3. Оценка на M : V × U
  2. MST: алгоритм Борувки
    1. Собственно алгоритм: фаза = выбрать для каждой вершины ребро min веса и сжать компоненты связности
    2. Чтобы не было циклов нужно, чтобы все веса были различными. Рассмотрим пары (wi, i)
    3. Оценка времени работы: O(ElogV)
    4. Избавляемся от кратных ребер цифровой сортировкой.
    5. Оценка времени работы с учетом удаления кратных ребер: O(V2), O(ElogE(V2))
  3. СНМ: Сжатие путей
    1. Амортизированная оценка на время работы m запросов = O((m+n)logn)
  4. Отрезки на прямой
    1. Выбрать максимальное количество неперескающихся отрезков на прямой
    2. Выбрать максимальное количество отрезков на прямой так, чтобы каждая точка была покрыта не более k раз
  5. Жадные алгоритмы
    1. Белоснежка и гномы, ai + bi
    2. Задача про 2 станка
    3. Автоматическое создание компаратора
    4. Школьники вылезают из ямы (РОИ 2006).
      1. Жадная часть
      2. Решение динамикой за O(n2)