Всем привет! Подскажите, как найти максимальное, но минимальное лексикографически паросочетание в уже двудольном графе?
Всем привет! Подскажите, как найти максимальное, но минимальное лексикографически паросочетание в уже двудольном графе?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Откуда задача?
Можно наивным путем — будем строить это паросочетание по одному ребру, пытаясь достичь лекс.минимальности, не потеряв при этом максимальность.
Сначала найдем размер макс.паросочетания. Пускай он равен Х.
Рассматриваем ребра по одному, начиная с лекс.минимального. Предположим, что какое-то ребро входит в ответ. Зафиксируем его и найдем макс.паросочетание в графе без смежных этому ребру вершин. Если размер этого паросочетания Х-1, то наше ребро входит в ответ. Если Х-2 или меньше, то не входит (потому что макс.паросочетание с этим ребром имеет размер не больше Х-1 и не является максимальным вообще). Далее аналогично находим следующие ребра ответа.
Лучше не искать новое паросочетание каждый раз заново.
Пусть у нас есть максимальное паросочетание. Построим ориентированный граф: ребра из паросочетания справа налево, остальные слева направо. Очевидно, что если найти в этом графе какой-то простой цикл, то половина его ребер из паросочетания, другая половина — не из паросочетания. Выбросим одни, добавим другие. Получим другое максимальное паросочетание.
Тогда, чтобы проверить есть ли максимальное паросочетание с конкретным ребром, нужно проверить есть цикл, содержащий это ребро. Если он есть — то PROFIT. Иначе можно доказать, что это ребро не лежит ни в каком максимальном паросочетании.
Итого проверяем одно конкретное ребро одним dfs, а не поиском максимального паросочетания.
Спасибо, просто и красиво)
Вариант с паросочетанием тоже не так уж и плох) Если хранить макс. паросочетание с предыдущего шага как образец, то мы можем тоже все пересчитывать быстро. В самом деле, размер паросочетания в графе, из которого мы выбросили ребро и смежные ему вершины — стал не хуже Х-2. Но он не может быть больше Х-1, потому что с удаленным ребром он не больше Х. Поэтому если взять за начальное приближение для Куна неиспорченную часть паросочетания-образца, то ее размер будет отличаться от оптимального не более чем на 1. И Куну нужно будет найти не более одной увеличивающей цепи.
Причем эту цепь нужно искать только из вершины, смежной удаленному ребру.
Вообще, идеи про поиск цепи и про поиск цикла -- они эквивалентны. Ведь если взять цикл и удалить данное ребро, то получится увеличивающая цепь. Но, подумав об этом, я нашел ошибку в своем "можно доказать, что.." :)
Контрпример: граф с ребрами 1-1, 2-2, 3-3, 1-2, 2-3, 3-4. В нем есть два максимальных паросочетания, но нет циклов. :(
Чтобы исправить мое утверждение про циклы, надо еще добавить исток и сток и ребра между истоком в левой долей и между стоком и правой долей. Опять же правильно их ориентировать. И теперь утверждение про цикл легко доказываться через циркуляцию потока.
А изначальное утверждение верно для графов с полным паросочетанием. Собственно, по памяти и сформулировал, не проверил и ошибся :)
В универе задали Полное условие здесь Мое решение — дихой ищу ответ, а затем проверяю куном. Однако из-за лексикографически минимального ответа падает решение.
"дихой" == дихотомией == двоичным поиском?
Просто интересно, нормально оно будет работать в худшем случае?
Ибо O(N3logC) -- достаточно много, ИМХО, чтобы влезть в TL.
Часть с дихотомией можно сделать быстрее — внутри бинарного поиска можно написать Хопкрофта-Карпа или Диница, а не Куна.
Чтоб наверняка — давай оно будет ещё и взвешенным :D
Оно, собственно, так и есть. =))
В условии действительно есть еще веса ребер. Вот только вес паросочетания -- это не сумма весов ребер, а минимум из весов ребер. :)
Ах, ну да. Хитро))
Тогда, конечно, все меняется.
Автор а подскажи, где ты учишься? Действительно интересно, у нас ничем подобным и "не пахнет", к сожалению..