Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 01 - про потоки

Краткий план лекции на тему "Потоки"

1. Алгоритмы поиска потока
2. [L,R] потоки
3. MinCost потоки и потоки минимального среднего веса
4. Паросочетания + задачи
5. Минимальное по весу контролирующее множество + задачи

Полный план лекции

1. Алгоритмы поиска потока
1. Эдмондс-Карп O(VE^2) + док-во (насыщение ребер, расстояния не убывают) + пример с макс временем работы
2. Масштабирование O(E^2logMax) + док-во (мин разрез, декомпозиция потока) + пример
3. Алгоритм Диница O(V^2E) + док-во + пример
4. Малхотра-Кумара-Махешвари O(V^3)
• Масштабирование + пуск максимума по пути = O(E^2)
• Диница + Масштабирование = O(VElogMax)
• Поток получается целочисленным
2. [L,R] потоки
1. MaxFlow = Flow + MaxFlow
2. Flow = задача про избытки-недостатки + бесконечное ребро (t,s)
3. Сведение задачи про избытки и недостатки к MaxFlow
4. Решение всего MaxFlow сразу бинпоиском от Ural SU Fusion
5. Решение задачи про округление матрицы, как пример к [L,R] потокам
3. MinCost потоки и потоки минимального среднего веса
1. MinCost = (+w,-w) + FordBelman
2. Если есть отрицательные циклы, можно и нужно их найти (тот же FordBelman)
3. Решение задачи про [L,R] потоки с помощью MinCost : (L,-inf) + (R-L,0)
4. Поток минимального среднего веса = BinSearch + MinCost c отрицательными циклами.
• * Проблема неориентированных ребер
• * Док-во корректности
• * Применение потенциалов Джонсона и Дейкстры
4. Паросочетания + задачи
1. Поиск паросочетания = последовательный поиск дополняющих чередующихся цепочек
2. Контролирующее множество (К.М.) и независимое множество (Н.М.) за O(E) по готовому паросочетанию
3. Поиск паросочетания с помощью потока за O(Flow)
4. MaxFlow --> MinCut --> К.М = A- and B+ ; Н.М. = A+ and B-
5. Алгоритм Хопкрофта-Карпа = Диница для паросочетаний за O(E*sqrt(V)), док-во через симм разность
6. Задачка о замощении доминошками доски с дырками (клетчатая доска = двудольный граф)
7. Задачка о замощении доски с дырками вертикальными и горизонтальными полосками (К.М. на графе строк и столбцов).
5. Минимальное по весу контролирующее множество + задачи
1. MinCut = MinCostCut : Sum{C[i]} ~ Sum{w[i]} ~ Sum{w[i]*c[i]}
2. MinCostCut --> Min К.М. и Max Н.М.
3. Решение задачи про инструменты. Замена минуса на плюс.
4. Решение задачи про матан. Бесконечные ребра не идут в MinCut.