|
Название задачи: Идем кругами . |
 |
Условие
Игровое поле представляет собой N кружков, некоторые из которых соединены отрезками. Каждому кружку приписана какая-то стоимость, а на каждом отрезке поставлена стрелка. Один из кружков является начальным, другой – конечным. Игрок должен переместить фишку из начального кружка в конечный, пройдя по каждому из отрезков ровно один раз. За перемещение по отрезку он получает определенное количество очков, равное стоимости кружка, в который он перемещается, взятой со знаком плюс, если движение происходит по направлению стрелки, и со знаком минус – если в противоположном.Требуется определить максимальное количество очков, которое может
набрать игрок в этой игре.
Входные данные
Входной файл содержит исходные данные в следующей последовательности:
N, x1, x2, ..., xN, b, q, M, u1, v1, u2, v2,
..., uM, vM. Здесь N – количество кружков (1 ≤ N ≤ 30), xi
– стоимость, приписанная i-му кружку (1 ≤ xi ≤
30 000), b и q – номера начального и конечного кружков (они могут совпадать), M –
количество отрезков, ui
и vi
– номера кружков, соединяемых i-м отрезком (направление стрелки – от ui
к vi). Два кружка могут быть соединены не более чем одним отрезком. Все числа во входном файле являются целыми и
разделяются пробелами и/или символами перевода строки.
Выходные данные
Вывести в выходной файл искомое количество очков и номера кружков, по
которым должен пройти игрок, чтобы набрать это количество. Номера кружков
должны быть записаны в порядке их посещения игроком. Если пройти из
начального кружка в конечный, удовлетворяя правилам игры, невозможно,
выходной файл должен содержать единственную строку «NO SOLUTION».
Пример входного файла
5 1 3 5 100 23
1 4
5
1 2
2 3
5 3
2 5
4 2
Пример выходного файла
-72
1 2 5 3 2 4
Решение
Заметим, что если пройти по каждому отрезку ровно один раз, то получится эйлеров путь. Проверка существования в графе такого пути осуществляется эффективно на основе критерия эйлеровости [Липский 87, п. 2.7]: граф должен быть связен (за исключением, быть может, изолированных вершин), и все вершины, за исключением начальной и конечной, должны иметь четную степень. Начальная же и конечная, если они не совпадают, – нечетную.Если мы установили существование в графе эйлерова пути, то дальше поиск пути с максимальной возможной суммой осуществляется перебором. Перед тем, как начинать перебор, имеет смысл найти какой-нибудь путь эффективным алгоритмом и запомнить его в качестве решения, наилучшего из найденных.
Пусть в процессе перебора мы уже построили некоторую начальную часть пути. Если добавление к суммарной стоимости этого пути всех оставшихся ребер графа, пройденных в направлении стрелок, не даст нам более хорошего решения, чем наилучшее на текущий момент, то следует делать отсечение.
Получив в процессе перебора некоторый путь, можно попытаться улучшить его, найдя в нем какой-нибудь цикл и изменив направление прохода по этому циклу на противоположное.
