ЛКШ 2016. Группа A. День 2. Потоки-2.

  1. C++
    1. Память: стек, куча, статическая
    2. int x[n]; // на стеке
    3. int *new[]()
    4. vector<bool>, vector<int>
    5. vector<int>::insert,erase
  2. Алгоритм Диница поиска потока
    1. Алгоритм. Отличие от Эдмондса-Карпа: каждый путь ищется за O(V). Получаем алгоритм за O(VE+VK) = O(V2E), где K − количество найденных путей.
    2. Запускаем алгоритм Диница внутри масштабирования. Получаем алгоритм за O(VElogU).
    3. Диниц для единичных сетей, одна фаза Диница работает за O(E).
  3. [L,R]
    1. Несколько истоков и стоков.
    2. Интересный факт: задача про 2 пути NP-трудна (объяснить в чём разница с 2 истоками, стоками)
    3. Потоки с избытками и недостатками потока в вершинах.
    4. Поиск [L,R] циркуляции. O(Flow).
    5. Поиск [L,R] потока, сведение к циркуляции за O(1).
    6. Поиск [L,R] максимального потока: дополнение до максимального. O(Flow).
  4. Min Cost Flow
    1. Задачи min cost circulation, min cost k-flow
    2. Сведение min cost k-flow к min cost circulation, решение min cost circulation алгоритмом Клейна.
    3. Корректность. Lm: mincost ⇔ не существует отрицательного цикла в остаточной сети
    4. Решение min cost k-flow для графа без отрицательных циклов за O(k*FordBellman)
    5. Потенциалы. Алгоритм Джонсона.
    6. Потенциалы. Решение min cost k-flow для графа без отрицательных циклов за O(k*Dijkstra).
    7. Задача о назначениях.
  5. [skipped] Хопркрофт-Карп для поиска паросочетания в двудольном графе, O(EV1/2).
  6. [skipped] Поиск [L,R] потока: решение через MinCostFlow