• Идем кругами
  GOGROUPS
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

Описание
Игровое поле представляет собой N кружков, некоторые из которых соединены отрезками. Каждому кружку приписана какая-то стоимость, а на каждом отрезке поставлена стрелка. Один из кружков является начальным, другой - конечным. Игрок должен переместить фишку из начального кружка в конечный, пройдя по каждому из отрезков ровно один раз. За перемещение по отрезку он получает определенное количество очков, равное стоимости кружка, в который он перемещается, взятой со знаком плюс, если движение происходит по направлению стрелки, и со знаком минус - если в противоположном

Задание
Требуется определить максимальное количество очков, которое может набрать игрок в этой игре


Входные данные
Входной файл содержит исходные данные в следующей последовательности: N, х₁,x₂,...,x_N, b,q, M, u₁,v₁,u₂,v₂,...,u_M,v_M. Здесь N - количество кружков (1N30), x_i - стоимость, приписанная i-му кружку (1х_i 30000), b и q -номера начального и конечного кружков (они могут совпадать), М - количество отрезков, u_i и v_i - номера кружков, соединяемых i-ым отрезком (направление стрелки - от u_i к v_i). Два кружка могут быть соединены не более чем одним отрезком. Все числа во входном файле являются целыми и разделяются пробелами и/или символами перевода строки

Выходные данные
Вывести в выходной файл искомое количество очков и номера кружков, по которым должен пройти игрок, чтобы набрать это количество. Номера кружков должны быть записаны в порядке их посещения игроком. Если пройти из начального кружка в конечный, удовлетворяя правилам игры, невозможно, выходной файл должен содержать единственную строку "NO SOLUTION"


Например:

GOGROUPS.IN
5 1 3 5 100 23
1 4
5
1 2
2 3
5 3 2 5 4 2

GOGROUPS.OUT
-72
1 2 5 3 2 4




Идеи
Перебор с отсечениями, эйлеров путь в графе

Комментарии
Заметим, что если пройти по каждому отрезку ровно один раз, то получится эйлеров путь. Проверка существования в графе такого пути осуществляется эффективно на основе критерия эйлеровости [Липский 87, п.2.7]: граф должен быть связен (за исключением, быть может, изолированных вершин), и все вершины, за исключением начальной и конечной, должны иметь четную степень. Начальная же и конечная, если они не совпадают, - нечетную

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

Получив в процессе перебора некоторый путь, можно попытаться улучшить его, найдя в нем какой-нибудь цикл и изменив направление прохода по этому циклу на противоположное




Решение
Авторское решение не представлено

© Особенности национальных задач по информатике