Итак, есть узлы: N = {1,...,n}
Есть списки узлов (пути), без повторяющихся элементов (циклов):
S1 = {1,2,3...}
S2 = {3,1,2...}
...
Каждый путь имеет некий вес, пусть i-тый путь имеет вес w[i].
Пути пересекаются, если имеют хотя бы один общий элемент.
Требуется найти не пересекающиеся пути так, чтобы сумма весов решения была максимальной.
Ограничения:
25 узлов, 50 000 путей
Подскажите, в какую сторону копать?
Али это намек на динамическое программирование?
Upd: а давай много путей будет - этак 50 тыс.
Можете описать задачу адекватнее, чем как огурцы ложкой банка майонеза?
Пока это выглядит как "Дано N множеств. Выберите из них наибольшее количество попарно не пересекающихся, с весами". В этой задаче надо копать к велосипеду, ибо без весов NPC
> Спасибо за идею. Посмотрим, подскажет ли комьюнити что-либо изящнее брутфорса.
И получит 1млн долларов от математического института Клэя за решение проблемы Кука.
ans = максимуму по всем маскам (d1[mask] + d2[mask]). В 256 мегабайт решение должно уложиться. Со временем хуже - n*2n. Скорее всего, это не влезет в ТЛ (если это надо скармливать тестеру), но покопать, думаю, можно)))
(d[mask] = max(w(mask) (вес пути, дающей эту маску), max d[mask AND(2n - 1 - (1 << i))] по всем i от 0 до n-1)).
Ваше решение верно, но m * 2n имеет ТЛ при m ~ 105...
какой-то подмаски, отличающейся от текущей на один бит)
1) Строим граф совместимости. Пересекаем хоть bitset-ом.
2) Это задача о максимальной клике (пусть с весами). Она решается за 2n / 2, n - число вершин.
50000 множеств, 25 элементов? Все наоборот?
А как задача о максимальной клике решается за 2n / 2?