Форд-Беллман, Флойд (18 ноября 2016)


  1. Форд-Беллман. Тестируем на случайном графе.
    1. Код, написанный в этом году: [code]
    2. Прошлогодний: [code] [code] [code]
    3. Стандартная реализация за Θ(VE), V = 105, E = 2 × 105
    4. Реализация с break − 22 итерации
    5. Реализация с очередью − в среднем меньше 2 итераций

  2. Задачи
    1. Нужно научиться на запрос "уменьшился вес ребра" за O(n2) пересчитывать матрицу расстояний.
    2. Проверить после этого, что нет отрицательных циклов
    3. Есть n валют и m обменников. i-й обменник предлагает менять валюту ai на валюту bi (орребро) по курсу ci/di. Можно ли, используя сколь угодно большие начальные сбережения и данные m обменников, сломать финансовую систему и бесконечно обогащаться? Считается, что у обменников есть бесконечное количество денег целевой валюты. O(nm).
    4. Upgrade: изначальные сбережения в рублях, в конце деньги тоже должны остаться в рублях.
    5. Есть ограф. Нужно найти количество необязательно простых путей из a в b
      1. Длины ровно k, здесь k ≤ 109.
      2. Длины не более k, здесь k ≤ 109.
      3. Длины от l до r, здесь l ≤ r ≤ 109.
    6. Цикл минимального среднего веса за O(VElogM)
    7. Цикл нулевого веса.
    8. Река (полоса). N точек-препятствий. Круг какого максимального радиуса можно провести по реке, не задевая препятствия.

  3. Доп задачи
    1. Даны 2N точек на плоскости, разбить их на пары, чтобы отрезки не пересекались