Надо найти Максимальное Независимое Множество на графе. Можете дать подсказку? На корневом дереве задача легко решается дпшкой dp[v][1, 0]. Но как на неориентированном графе где N≤40, M ≤ n * (n - 1) / 2. На ум приходит как то перебрать подмножества.
1 лайк
N \leq 40 - скорее всего mitm
Дальше думай сам, все просто
upd:
Ну допустим ты разделил вершины на две группы по n/2 вершин.
Пусть ты выбрал маску вершин m1 с первой группы и маску вершин m2 с второй группы. И мы знааем что вершины из маски m1 формируют независимое множество вершин и вершины из маски m2 формируют независимое множество, как проверить что если выбрать вершины из m1 и m2 то в итоге получится независимое множество?
Решение:
Пусть G[M] = 1 если вершины из маски M являются независимым множеством, иначе G[M] = 0.
Введём массив sosedi[v], i-ый бит sosedi[v] будет равен 1 если между v и i есть ребро, иначе этот бит будет равен 0.
Пусть Z[m1] - or всех sosedi[v] где v это вершина входящая в маску m1. Теперь условие того что маски m1 и m2 совместимы такое :
Z[m1] \& m2 = 0<=>BitReverse(Z[m1]) \& m2 = m2
G[m1] = 1 и G[m2] =1.
Теперь задача состоит в том чтобы просто посчитать для каждой маски подмаску максимального размера с G[mask] = 1. (В тупую дп по маскам)
Остальное легко додумывается, нужно просто реализовать всё.
3 лайка