Потоки (13 апреля 2015)

  1. Теория
    1. Scaling, версии за O(E2logU) и ~O(E2)
    2. Декомпозиция потока за O(E2)
  2. Теория в форме задач
    1. k непересекающихся путей
    2. Вершинный поток
    3. Ориентированный и неориентированный граф
    4. Несколько истоков и стоков
    5. Избытки и недостатки
    6. [L,R]-циркуляция
    7. [L,R]-поток
  3. Задачи про поток
    1. Поиск паросочетания в двудольном графе
    2. Поиск мульти паросочетания, старая задача про самолёты
    3. Поиск контролирующего множества Min веса, независимого множества max веса
    4. Турнирная таблица
    5. Восстановление матрицы
  4. Кодим
    1. Поток [code]
    2. Чуть более быстрый поток [code]
    3. Декомпозиция потока [code]
  5. [не успеем] Минимальный разрез (количество рёбер)
    1. [не успеем] Единственность
    2. [не успеем] Минимальный и максимальный