Потоки

Понедельник, 13 апреля 2015
Таймс, ауд. 404

Описание

  • Теория
    • Scaling, версии за \(O(E^2logU)\) и ~\(O(E^2) \)
    • Декомпозиция потока за \(O(E^2)\)
  • Теория в форме задач
    • k непересекающихся путей
    • Вершинный поток
    • Ориентированный и неориентированный граф
    • Несколько истоков и стоков
    • Избытки и недостатки
    • [L,R]-циркуляция
    • [L,R]-поток
  • Задачи про поток
    • Поиск паросочетания в двудольном графе
    • Поиск мультисочетания, старая задача про самолёты
    • Поиск контролирующего множества Min веса, независимого множества max веса
    • Турнирная таблица
    • Восстановление матрицы
  • Кодим
    • Поток
    • Чуть более быстрый поток
    • Декомпозиция потока