Всем привет! Подскажите, как найти максимальное, но минимальное лексикографически паросочетание в уже двудольном графе?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 13:29:25 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Откуда задача?
Можно наивным путем — будем строить это паросочетание по одному ребру, пытаясь достичь лекс.минимальности, не потеряв при этом максимальность.
Сначала найдем размер макс.паросочетания. Пускай он равен Х.
Рассматриваем ребра по одному, начиная с лекс.минимального. Предположим, что какое-то ребро входит в ответ. Зафиксируем его и найдем макс.паросочетание в графе без смежных этому ребру вершин. Если размер этого паросочетания Х-1, то наше ребро входит в ответ. Если Х-2 или меньше, то не входит (потому что макс.паросочетание с этим ребром имеет размер не больше Х-1 и не является максимальным вообще). Далее аналогично находим следующие ребра ответа.
Лучше не искать новое паросочетание каждый раз заново.
Пусть у нас есть максимальное паросочетание. Построим ориентированный граф: ребра из паросочетания справа налево, остальные слева направо. Очевидно, что если найти в этом графе какой-то простой цикл, то половина его ребер из паросочетания, другая половина — не из паросочетания. Выбросим одни, добавим другие. Получим другое максимальное паросочетание.
Тогда, чтобы проверить есть ли максимальное паросочетание с конкретным ребром, нужно проверить есть цикл, содержащий это ребро. Если он есть — то PROFIT. Иначе можно доказать, что это ребро не лежит ни в каком максимальном паросочетании.
Итого проверяем одно конкретное ребро одним dfs, а не поиском максимального паросочетания.
Спасибо, просто и красиво)
Вариант с паросочетанием тоже не так уж и плох) Если хранить макс. паросочетание с предыдущего шага как образец, то мы можем тоже все пересчитывать быстро. В самом деле, размер паросочетания в графе, из которого мы выбросили ребро и смежные ему вершины — стал не хуже Х-2. Но он не может быть больше Х-1, потому что с удаленным ребром он не больше Х. Поэтому если взять за начальное приближение для Куна неиспорченную часть паросочетания-образца, то ее размер будет отличаться от оптимального не более чем на 1. И Куну нужно будет найти не более одной увеличивающей цепи.
Причем эту цепь нужно искать только из вершины, смежной удаленному ребру.
Вообще, идеи про поиск цепи и про поиск цикла -- они эквивалентны. Ведь если взять цикл и удалить данное ребро, то получится увеличивающая цепь. Но, подумав об этом, я нашел ошибку в своем "можно доказать, что.." :)
Контрпример: граф с ребрами 1-1, 2-2, 3-3, 1-2, 2-3, 3-4. В нем есть два максимальных паросочетания, но нет циклов. :(
Чтобы исправить мое утверждение про циклы, надо еще добавить исток и сток и ребра между истоком в левой долей и между стоком и правой долей. Опять же правильно их ориентировать. И теперь утверждение про цикл легко доказываться через циркуляцию потока.
А изначальное утверждение верно для графов с полным паросочетанием. Собственно, по памяти и сформулировал, не проверил и ошибся :)
В универе задали Полное условие здесь Мое решение — дихой ищу ответ, а затем проверяю куном. Однако из-за лексикографически минимального ответа падает решение.
"дихой" == дихотомией == двоичным поиском?
Просто интересно, нормально оно будет работать в худшем случае?
Ибо O(N3logC) -- достаточно много, ИМХО, чтобы влезть в TL.
Часть с дихотомией можно сделать быстрее — внутри бинарного поиска можно написать Хопкрофта-Карпа или Диница, а не Куна.
Чтоб наверняка — давай оно будет ещё и взвешенным :D
Оно, собственно, так и есть. =))
В условии действительно есть еще веса ребер. Вот только вес паросочетания -- это не сумма весов ребер, а минимум из весов ребер. :)
Ах, ну да. Хитро))
Тогда, конечно, все меняется.
Автор а подскажи, где ты учишься? Действительно интересно, у нас ничем подобным и "не пахнет", к сожалению..