Паросочетания

1. [Сережа.K] C/C++
1. static int x = 0;
2. inline
3. random_shuffle
4. printf("%-*s : %.2fn", 20, "abc", sqrt(2.0))
5. scanf("%d") → getchar(), readUInt()
2. [Сережа.K] Паросочетание
1. Определения: mathcing, cover, independent set, global cut
2. min cover ≥ max matching
3. Лемма для произвольного графе: паросочетание не максимально ⇒ существует дополняющий чередующийся путь
4. Для доказательства леммы изучаем симметрическую разность с максимальным паросочетанием.
5. Научимся в двудольном графе искать дополняющий чередующийся путь за O(E)
6. Реализация: dfs, used[вершина первой доли], pair[вершина второй доли]
7. Простой алгоритм за O(VE): пока есть путь, ищем путь
8. Алгоритм Куна за O(VE): от каждой вершины запускаем один раз dfs
9. Жадная инициализация: можно как минимум половину паросочетания построить за O(E)
10. A⁺, A^-, B⁺, B^-: по готовому паросочетанию за O(E) ищем cover, independent set
11. Паросочетание, которое максимизирует суммарный вес вершин первой доли (док-во: матроид)
12. Еще паросочетание умеют искать за O(EqsrtV): алгоритм Хопкрофта-Карпа
13. Рандомизированный алгоритм поиска паросочетания в произвольном графе
3. [Сережа.K] Задачи про паросочетания
1. [matching] Доминошки на доске с дырками
2. [matching] Taxi: покрытие ацикличного графа путями
3. [independent] Максимальная клика (или антиклика) в двудольном графе
4. [cover] Замощение грида минимальным числом палок 1xN
5. [homework] В каком случае ребро лежит в каком-то максимальном паросочетании?
6. [homework] В каком случае ребро лежит в любом максимальном паросочетании?
7. Стабильное паросочетание (мальчики предлагают, девочки отказываются)