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

vb = <font color=green>[Ваня]</font>
sk = <font color=darkblue>[Сережа.K]</font>
sm = <font color=darkred>[Сережа.М]</font>

# $sk$ C/C++
## <code>static int x = 0;</code>
## <code>inline</code>
## <code>random\_shuffle</code>
## <code>printf("%-*s : %.2f\n", 20, "abc", sqrt(2.0))</code>
## <code>scanf("%d") &rarr; getchar(), readUInt()</code>
# $sk$ Паросочетание
## Определения: mathcing, cover, independent set, global cut
## min cover &ge; max matching 
## Лемма для произвольного графе: паросочетание не максимально &rArr; существует дополняющий чередующийся путь
## Для доказательства леммы изучаем симметрическую разность с максимальным паросочетанием.
## Научимся в двудольном графе искать дополняющий чередующийся путь за O(E)
## Реализация: dfs, used[вершина первой доли], pair[вершина второй доли]
## Простой алгоритм за O(VE): пока есть путь, ищем путь
## Алгоритм Куна за O(VE): от каждой вершины запускаем один раз dfs
## Жадная инициализация: можно как минимум половину паросочетания построить за O(E)
## A^{+}, A^{-}, B^{+}, B^{-}: по готовому паросочетанию за O(E) ищем cover, independent set
## Паросочетание, которое максимизирует суммарный вес вершин первой доли (док-во: матроид)
## Еще паросочетание умеют искать за O(EqsrtV): алгоритм Хопкрофта-Карпа
## Рандомизированный алгоритм поиска паросочетания в произвольном графе
# $sk$ Задачи про паросочетания
## [matching] Доминошки на доске с дырками
## [matching] Taxi: покрытие ацикличного графа путями
## [independent] Максимальная клика (или антиклика) в двудольном графе
## [cover] Замощение грида минимальным числом палок 1xN
*## В каком случае ребро лежит в каком-то максимальном паросочетании?
*## В каком случае ребро лежит в любом максимальном паросочетании?
## Стабильное паросочетание (мальчики предлагают, девочки отказываются)