Возьмём множество из всех атомов. Найдём отсутствующее ребро, у которого оба атома в множестве. Понятно, один из них надо исключить, переберём какой, уходим в рекурсию. Если всё ок — берём сумму атомов во множестве и улучшаем ответ.

Так как мы можем исключить всего 16 атомов (50/3) , то и ветвлений всего 2^16.

Должен работать такой перебор: Берем все вершины и находим наименьшую пару (i, j) что между i и j нет ребра. Рекурсивно перебираем, выкинув либо i либо j. Т.к. глубина не больше n/3, получаем O(2^(n/3))

где n — количество максклик(которые нельзя увеличить)
автор ниже прав, я не умею читать :(

У меня алгоритм Брона-Кербоша зашел в практике после отсечения (если кандидатов не хватит на достаточно большую клику), максимум 684 мс. Подскажите, это дырка в тестах или правда этого отсечения достаточно? http://pastebin.com/icARB4fb

compile нажимал, или только run tests?

я так понимаю она идентична div1 500? Она обсуждаеться выше

Для начала создадим порядок в обходе всех ребер. Теперь пустим рекурсию по состоянию. В начале у нас пустое множество. Пусть на каком-то шаге у нас образовалось мн-во А, |A| = t. Найдем все ребра вершины которых не лежат в A. Если таких ребер не нашлось, то из вершин не лежащих в А возьмем k-t вершин с максимальным весом добавим и обновим ответ. Иначе возьмем первое ребро и закинем сперва первую вершину, а затем вторую. В итоге у нас получается О(n * n * 2^k).

Казалось бы, падает на полном графе, в котором удалено штук десять ребер.