Алгоритм Построения Наибольшего паросочетания через потоки
- добавим вершину s и всевозможные ребра (s,x), где x принадлежит доли Х добавим вершину t и всевозможные ребра (y,t), где y принадлежит доли Y
- Провесим весь граф весом равным единице
- построим максимальный поток (Алгоритм Форда Фолкерсона)
- удалим вершины s,t и соответствующие ребра, получим наибольшее паросочетание