Пусть задан двудольный граф. И пусть все рёбра, которые в нём есть, имеют единичную пропускную способность. Рёбра заданы матрицей смежности: строки будут соответствовать первой доле графа, а столбцы - второй.
Для каждой вершины графа известно, сколько инцидентных ей рёбер нужно пометить. После того, как мы пометим
необходимое количество рёбер, требуется вывести на экран модифицированную матрицу смежности: на месте помеченного ребра писать "Y", а на месте непомеченного или отсутствующего "N". Среди всех возможных вариантов ответа нас интересует минимальный лексикографически (если нумеровать символы сверху-вниз, слева-направо).
Как такую задачу решать? Понятно, что можно свести её к min-cost-max-flow, обозначив веса степенями двойки, но при ограничениях, скажем 100*100, это не очень приятно делать. Возможно, есть другой алгоритм?
В приложенном плане лекций ЛКШ (тема 6) упоминается алгоритм максимального паросочетания, минимального лексикографически. Может ли кто-то рассказать этот алгоритм? Даже если задача из плана отличается от того, что я привёл, всё равно будет интересно прочитать.
Заранее благодарю.