Модуль: Паттерны в динамическом программировании - 2


Задача

4 /5


Гном

Теория Нажмите, чтобы прочитать/скрыть

Дисклеймер: способ, описанный ниже, не является универсальным, однако зачастую может решить задачу или помочь прийти к правильному решению.

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

Основным параметром будет являться битовая маска, которая будет показывать какие элементы уже были включены в перестановку, а какие нет. Также часто требуется второй параметр, который показывает, какой элемент был включен последним.

Часто перестановки можно увидеть в контексте путей в графах. Соответственно рассмотрим классический пример - задача о гамильтоновом пути.
Гамильтонов путь - это простой путь, проходящий через каждую вершину графа ровно один раз. Его можно представить просто как перестановку длины n, где n - количество вершин. Порядок внутри этой перестановки будет обозначать порядок обхода вершин в этом пути.

Для того, чтобы проверить наличие гамильтонова пути в графе, заведем динамику dp[mask][last] - существует ли простой путь, который обошел вершины, помеченные единицами в битовой маске mask и при этом закончил в вершине last.
Начальные значения будут dp[2i][i] = true, остальные false, что означает, что всегда есть пустой путь, начинающийся в любой из вершин.
Имея значение true в dp[mask][last] будем делать переходы вперед, по смыслу "продлевая путь". То есть будем искать номера вершин, которые помечены нулем в mask (мы их еще не посещали в пути) и при этом такие, что есть ребро из last в эту вершину (путь должен быть продлен существующим ребром). То есть делаем dp[mask | 2k][k] = true, если dp[mask][last] = true И mask & 2k = 0 (вершину k еще не посещали) И есть ребро last -> k.
В конечном итоге гамильтонов путь существует, если есть значение true в dp по параметрам битовой маски, состоящей только из единиц, и любой последней вершины.

Задача

Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено N точек, в которых может находиться клад. Все точки пронумерованы числами от 1 до N. Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером 1. Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером 1 никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.

Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.

Входные данные
В первой строке находится одно целое число N (1 ≤ N ≤ 15) — количество точек, отмеченных на карте. В последующих N строках находятся расстояния между точками. В (i+1)-й строке находятся N целых чисел di1,di2, diN — длины дорог от i-й точки до всех остальных. Гарантируется, что dij=dji, dii=0 и 0 <dij <100. В (N+2)-й строке находится одно целое число Q (1 < Q ≤ 1000) — количество вариантов вычеркивания точек для данной карты. В последующих Q строках содержится описание вариантов вычеркивания. Описание начинается с числа C (0 ≤ C < N) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие C чисел задают номера этих точек.

Выходные данные
Выведите Q строк. В каждой строке выведите одно целое число — длину минимального маршрута при соответствующем варианте вычеркивания точек.
Примеры
Входные данные Выходные данные
1 3
0  45 10
45 0  30
10 30 0
2
0
1 3
40
45
2 5
0  14 20 17 14
14 0  15 19 18
20 15 0  15 16
17 19 15 0  14
14 18 16 14 0
2
3 5 4 3
0
14
58