Графическая проблема

Question

Я изо всех сил пытаюсь решить следующую проблему

http://uva.onlinejudge.org/external/1/193.html

Однако я не могу найти быстрое решение.

И как видно по временам других, должно быть решение максимальной сложности n ^ 2

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problemid=129&page=problem_stats

Могу ли я получить некоторую помощь?

Answer 1

Вы можете решить эту проблему только по экспоненциальной сложности, но это не так плохо, как кажется, потому что на практике вы сможете избежать многих плохих решений и, таким образом, значительно сократить время работы алгоритма.

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

Если вы не можете понять это, то проверьте эти два фрагмента кода, которые я нашел, прибегая к поиску имени проблемы: one и два .Авторы говорят, что они получают AC, но я не проверял их.Однако они выглядят правильно.

Answer 2

Алгоритм Брон-Кербоша

Я решил похожую проблему на головоломках FaceBook, для этого я использовал алгоритм BK.

Answer 3

Это решение проблемы, называемой максимальной кликой, также называемой максимальным независимым набором или максимальным стабильным набором. Это NP-Complete. Самый быстрый код, который я знаю для маленьких графиков, это Cliquer: http://users.tkk.fi/pat/cliquer.html

Если вы пишете свои собственные для образовательных целей, то, вероятно, наиболее эффективно выполнять поиск в глубине, сначала окрашивая узлы в черный цвет по одному и отступая вверх по DFS, если два черных узла касаются.

Самое простое в коде решение - реализовать двоичный счетчик и попробовать все 2 ^ n возможностей.