задача про домино, поиск наибольшей замыкающейся последовательности Опции

[Zenon]

Здравствуйте.
Поставили перед нами такую задачe. Дано n кубиков домино, как известно они имеют номера с двух сторон, но в задаче сказано, что для данного случая они не ограничены цифрой 6, т.е. значения с обеих сторон могут быть боле 6, например 16 и 12 и т.п. (какие - то разумные пределы конечно есть, но просто больше чем в настоящих, т.е. чем 6). Задние состоит в том, чтобы найти самую длинную замкнутую цепочку.... Если честно теряюсь в догадках и по вопросу алгоритма и по вопросу реализации....
Надеюсь на Вашу помощь.

[volvo]

Кстати, volvo, мой ТС 3.0 не понимает "int m[max_num + 1][max_num + 1] = {};"

Ребят, вам шашечки, или ехать? Первая программа работала на TC - не понравилось, теперь работает в ICC/GCC - опять нехорошо...

[Michael_Rybak]

Ура!

Короче я вот спросил на форуме TopCoder'a, и там ulzha родил гениальную мысль.

Вот полученная им цепочка рассуждений:

1. Представим все возможные числа на доминошках - вершинами в графе, а сами доминошки - ребрами. Теперь перед нами стоит задача построения самого длинного замкнутого маршрута, проходящего через каждое ребро не больше 1 раза, а через каждую вершину - произвольное кол-во раз.

2. Пусть в графе n вершин и m ребер. Добавим к каждой вершине цикл длины m+1, т.е. m новых, фиктивных вершин.

Получится, что, если в начальном графе существовал замкнутый маршрут, проходящий через каждую вершину как минимум один раз, то в новом графе, дополненном циклами, обязательно существует маршрут длины большей, чем n*(m+1) - ведь из каждой вершины мы можем пройтись по ее дополнительному циклу.

Понятно, что верно и обратное утверждение: получить в новом графе маршрут длины большей, чем n*(m+1), можно *только* посетив каждую вершину оригинального графа как минимум один раз.

3. M. R. Garey, D. S. Johnson и R. Endre Tarjan показали, что поиск гамильтонова цикла в планарном, кубическом, 3-связном графе является NP-полной задачей.

4. Кубический граф - такой, у которого степень каждой вершины равна 3. Получается, замкнутый маршрут в таком графе не может побывать в какой-нибудь вершине больше одного раза - ведь это означало бы, что ее степень - как минимум 4.

5. Сведем это воедино.

• Рассмотрим кубический, планарный, 3-связный (n, m) граф. Добавим к каждой вершине цикл длины m+1.
• Найдя такой цикл, мы однозначно сможем определить (критерий - ребер в найденном цикле больше n(m+1)), существует ли в изначальном графе цикл, проходящий через каждую вершину как минимум 1 раз; если существует, то мы его уже построили - просто удаляем фиктивные ребра из ответа
• В кубическом графе никакой цикл не может проходить в какую-нибудь вершину больше 1 раза, поэтому фактически мы научились строить гамильтонов цикл (в случае его существования)
• Итак, мы свели NP-полную задачу к исходной, т.е. показали, что, умея решать задачу про доминошки за полиномиальное время, научимся решать за такое же время NP-полную задачу.

Браво, ulzha!