ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102922
Темы:    [ Перебор с отсечениями ]
[ Эйлеров цикл ]
Сложность: 3+
Классы:
Название задачи: Идем кругами .
В корзину
Прислать комментарий

Условие

Игровое поле представляет собой 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]: граф должен быть связен (за исключением, быть может, изолированных вершин), и все вершины, за исключением начальной и конечной, должны иметь четную степень. Начальная же и конечная, если они не совпадают, – нечетную.

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

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

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

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 2
Название Перебор с возвратом
гЮДЮВЮ
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .