Сервер олимпиад

Ставропольский государственный университет

Имя
Пароль

Server Off-Line
Server time: 29 Mar 2024 10:18:40

Банк задач


Номер задачи - 7

Задача Цивилизация

Ограничение: 2 сек. на тест.

В некоторых стратегических играх, в частности в Civilization, игрок берет на себя роль правителя цивилизации, и целью игры является ее развитие, начиная с каменного века, с попутным уничтожением всех противников. Для достижения прогресса, цивилизация должна добывать научные знания (технологии). Новые технологии могут быть основаны на ранее открытых, и таким образом возникают зависимости. Например, изобретение книгопечатания невозможно без изобретения письменности.

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

Например, если цель игрока — победить всех соперников на самом раннем этапе развития, то ему совершенно не нужны Computers, Robotics или Space Flight, а вещи вроде Mobile Warfare, Nuclear Fission, Rocketry или Explosives были конечно весьма кстати, но требуют развить слишком много других, бесполезных для его целей технологий.

Формально, для каждой технологии задана ее полезность — некоторое целое число. Полезные технологии, вполне логично, имеют более высокое (положительное) значение полезности, а бесполезные — отрицательное значение (и чем больше трудоемкость исследований, тем оно меньше). Требуется найти подмножество технологий S (возможно даже пустое), такое что сумма их полезностей максимальна, и для каждой технологии из S, все технологии от которых она зависит также включены в S.

Формат входных данных

Каждая строка входного файла содержит описание одной технологии в следующем формате (поля разделяются пробелами): название технологии, полезность технологии, технологии требуемые для начала ее развития. Название технологии состоит из латинских букв, и имеет длину не больше 50 символов. Общее число технологий не превышает 30. Полезность технологии — целое число, по абсолютному значению не превосходящее 105.

Гарантируется, что во входном файле не будет циклических зависимостей (вроде: X требует Y, Y требует Z, Z требует X). Каждая технология, от которой зависит другая технология будет обязательно описана на какой-то строке входного файла.

Формат выходных данных

Выведите одно целое число — суммарная полезность выбранного вами подмножества технологий.

Примеры
ВходВыход
Alphabet -500
Mathematics 2000 Alphabet Masonry
Masonry -100
Writing -200 Alphabet
CodeOfLaws -400 Alphabet
Literacy 700 Writing CodeOfLaws
CeremonialBurial -200
Religion 150 CeremonialBurial
1500

Замечание к примеру: следует выбрать Mathematics и Literacy, и все технологии, от которых они прямо или косвенно зависят.


1. Open-source клон "Цивилизации" — Freeciv — можно скачать здесь.

Rambler's Top100 | Карта сайта | Контакты | Copyright © 2005-2007, Ставропольский государственный университет.