Сведение к паросочетанию

Алгоритм занимает двадцать строк, сведение — шестьдесят, и ошибки живут в сведении. Соберём приёмы, которые встречаются чаще всего.

Где искать две доли

в условии	доли	ребро
таблица, «не больше одного в строке и в столбце»	строки и столбцы	клетка
доминошки, плитки $1 \times 2$	клетки по чётности $i + j$	соседство
ходы коня, «квадрат расстояния равен 5»	то же	ход
ладьи с препятствиями	отрезки строк и отрезки столбцов	клетка
слоны с препятствиями	отрезки диагоналей двух направлений	клетка
расписание, «после этого можно то»	событие как предшественник и как преемник	«успеваем»
вложенность, делимость, включение	элемент как меньший и как больший	сравнимость

Шахматная раскраска

Самый частый способ увидеть двудольность там, где её не видно. Красим клетки по чётности $i + j$. Годится всюду, где связь всегда меняет эту чётность:

• доминошка накрывает соседние клетки — чётность меняется;
• ход коня меняет одну координату на $1$, другую на $2$ — чётность меняется;
• вообще любой ход, у которого сумма смещений нечётна.

А вот ход слона чётность не меняет, и раскраска для него бесполезна — там работает другой приём, разрезание диагоналей на отрезки.

Отрезки вместо строк

Если фигура бьёт вдоль прямой, но препятствия загораживают, разрежьте каждую прямую на максимальные отрезки свободных клеток. Клетка лежит ровно в одном отрезке каждого направления, а «не больше одной фигуры на отрезке» — это и есть паросочетание.

Для ладей направления — строки и столбцы; для слонов — диагонали $i - j$ и $i + j$.

Ёмкости

Если вершина правой доли принимает до $c$ соседей, можно завести $c$ её копий — но проще поменять одну строчку в Куне:

if (load[j] < capacity[j]) { residents[j].push_back(u); load[j]++; return true; }
for (int w : residents[j])
    if (tryAssign(w)) { replace(j, w, u); return true; }   // переселяем любого

Обычный Кун — частный случай при всех $c = 1$.

Если ёмкости нужны с обеих сторон, паросочетания уже мало: это задача о потоке.

Двоичный поиск снаружи

Вопрос «максимизировать минимальный вес» или «минимизировать максимальный» решается двоичным поиском по значению, внутри которого стоит обычное паросочетание:

bool feasible(int x) { return maxMatching(edgesNotWorseThan(x)) == best; }

Искать надо по списку встречающихся значений, а не по отрезку: ответ обязательно равен одному из них. Направление монотонности выпишите до того, как писать поиск, — перепутать «максимум минимума» и «минимум максимума» легко.

Веса на вершинах

Если веса стоят не на рёбрах, а на вершинах одной доли, и надо максимизировать сумму весов покрытых вершин, работает жадность: сортируем по убыванию веса и по очереди пробуем добавить каждую вершину поиском увеличивающего пути.

Причина — множества одновременно покрываемых вершин образуют трансверсальную матроиду, а на матроиде жадный выбор оптимален (теорема Радо — Эдмондса). Вершины с неположительным весом просто пропускаются.

Для весов на рёбрах это не работает: там нужен венгерский алгоритм или поток минимальной стоимости.

Проверка себя

Прежде чем писать, посчитайте ответ руками на вырожденных случаях: граф без рёбер, полный двудольный граф, доска целиком из препятствий, одна вершина в доле. Половина ошибок в сведении видна уже на них.