Программирование основных алгоритмов 8. Алгоритм Диница и Хопкрофта-Карпа. Строки (начало)

Программирование основных алгоритмов. МФТИ, Физтех-школа прикладной математики и информатики.

Дата лекции: 29.03.2023
Лектор: Кулапин Артур Евгеньевич

00:00:00 - интро
00:00:04 - напоминание схемы Форда-Фалкерсона
00:01:51 - слоистая сеть, блокирующий поток
00:07:23 - схема Диница
00:11:03 - оценка количества итераций схемы Диница
00:17:35 - поиск блокирующего потока: удаляющий обход
00:33:24 - псевдокод удаляющего обхода
00:42:25 - с+, с-, φ(v), φ(N)
00:44:43 - теорема Карзанова и её применение
00:50:20 - алгоритм Хопкрофта-Карпа
00:55:40 - строки
00:56:54 - задачи на следующие лекции

Монтажер: Вашкевич Егор
Оператор: Вашкевич Егор

Видео Программирование основных алгоритмов 8. Алгоритм Диница и Хопкрофта-Карпа. Строки (начало) канала Лекторий ФПМИ