Идея максимального паросочетания кажется очевидной. Только надо проверить что оно полное и единственное. Первое проверяется легко. Про второе я забыл и обнаружил после получения WA на первом тесте (да, не проверил стандартный тест). Времени оставалась мало и надо было что-то придумать для проверки единственности. Первое что пришло это по очереди блокировать (т.е. запретить использование) каждый город, который входит в паросочетание и пробовать найти другое паросочетание. Сдав задачку в темную и получив после ОК я вроде и не думал о ней, пока не стал рассказывать идею решение своему другу. И как я вообще мог дойти до такой идеи, ведь правильно надо было блокировать ребро, а не город. Кому интересно вот решение.
Слабость тестов мне кажется очень очень плохо сказывается на подготовке, ведь все что придумывается на тренировках может в дальнейшем использоваться на серьезных соревнованиях. Поэтому хочется попросить всех авторов более серьезно относиться к подготовке задач. Спасибо за внимание.
Я думаю это связано с тем, что есть решение (и я думаю, что авторское такое же) вообще без поиска паросочетаний
Это жадность? На днях primorial рассказал одну, но вот контр пример и неинтуитивное доказательство придумать не смог.
Ответил ниже
Кстати. У меня прошла такая жадина: если количество полков (n) не равно количеству всевозможных пунктов назначения, то ответ -1 (либо ответ будет не единственный, либо его не будет вообще), иначе нужно построить на этих вершинах n пар. Сделаем n следующих итераций: находим пункт назначения, в который из оставшихся полков может прийти только один полк, ведём туда этот полк и удаляем у остальных пунктов назначения этот полк, если же нет такого пункта назначения, у которого ровно один возможный полк, то опять же либо в итоге нельзя будет построить n пар, либо будет не единственный вариант ответа. Если смогли проделать n итераций, то нашли ответ.
Прикол в том, что это решение прошло, а решение в котором я делал тоже самое, только искал не пункты назначения с одним полком, а полки с одним возможным пунктом назначения к текущему шагу, получало WA5 (может быть я ошибся где-то в этой реализации, может тесты слабые). Вообще правильна ли такая жадина? Я не смог придумать плохой тест.
Ошибся в реализации (у меня тоже была ошибка и тоже 5й тест). Это правильное решение. Пусть у нас в какой-то момент остается граф, в котором есть полное паросочетание, и при это степени всех вершин слева больше 1. Тогда построим другое паросочетание — возьмем любую вершину справа, перейдем по ребру паросочетания налево. Затем перейдем по ребру не из паросочетания направо (очевидно такое есть так как из каждой вершины ребер более 2х). Продолжим процесс пока не вернемся в одну из посещенных вершин. У нас образовался цикл, в котором каждое второе ребро из паросочетания. Мы можем теперь заменить ребра по циклу и получили другое паросочетание
Wow. Круто.. я обрадовался, что установил собственный рекорд, сдав задачу за 2 секунды до окончания, но потом чуть огорчился, потому что подумал, что фигню заслал. Здорово, я снова рад! :)
Раз не доказал, то фигню заслал. Какая разница, что она при этом правильная? :)
Ну как бы я же не просто так засылал. Я думал, конечно, о том, что если не осталось вершин с одной связью, значит будет образовываться цикл, а значит два ответа, или не будет вообще ответа, но я не доказывал это чётко.
"...Продолжим процесс пока не вернемся в одну из посещенных вершин..." или пока не попадем в свободную от паросочетания вершину справа, так?
Таких нет так как паросочетание полное
да, но правая доля по размеру больше левой...
Мы же уже выяснили, что справа столько же вершин с хотя бы одним ребром, сколько и слева
не понимаю... ну вот пример:
Тогда если мы оставим только ребро 1 1 и забудет о 1 2, то получится единственное паросочетание...
Ну, так в данном случае не пустых вершин справа больше, чем слева, поэтому ответ -1
понял, надо было ещё раз прочитать комментарий от AndreySiunov
Кто-нить в курсе, Snark сейчас следит за системой? А то новостей на главной нету ни по 4, ни по 3 раунду.