1 Тема от olpetOdessaONU Отредактировано olpetOdessaONU (2011-04-30 22:42:38)

  • Откуда: Одесса
  • Зарегистрирован: 2010-12-15
  • Сообщений: 1

Тема: Максимальный поток, минимальный лексикографически

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

Для каждой вершины графа известно, сколько инцидентных ей рёбер нужно пометить. После того, как мы пометим
необходимое количество рёбер, требуется вывести на экран модифицированную матрицу смежности: на месте помеченного ребра писать "Y", а на месте непомеченного или отсутствующего "N". Среди всех возможных вариантов ответа нас интересует минимальный лексикографически (если нумеровать символы сверху-вниз, слева-направо).

Как такую задачу решать? Понятно, что можно свести её к min-cost-max-flow, обозначив веса степенями двойки, но при ограничениях, скажем 100*100, это не очень приятно делать. Возможно, есть другой алгоритм?

В приложенном плане лекций ЛКШ (тема 6) упоминается алгоритм максимального паросочетания, минимального лексикографически. Может ли кто-то рассказать этот алгоритм? Даже если задача из плана отличается от того, что я привёл, всё равно будет интересно прочитать.

Заранее благодарю.

Post's attachments

plan-A0.pdf 69.27 kb, 12 downloads since 2011-04-30 

You don't have the permssions to download the attachments of this post.

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Максимальный поток, минимальный лексикографически

Можно подбирать ребра по одному. Просто добавляем ребро, а затем потоком проверяем, можем ли мы остальное достроить так чтобы все ограничения выполнялись. Нам не нужно каждый раз поток полностью пересчитывать, достаточно поиска одного дополняющего пути. Сложность O(E^2), хотя константа, думаю, будет маленькой.