Версия для печати
Убрать все задачи
Игровое поле представляет собой 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
Решение
Все источники
>>
Книги, журналы
>>
Алфутова Н.Б., Устинов А.В., Алгебра и теория чисел
>>
глава 1. Метод математической индукции
