|
Название задачи: Золотая лихорадка . |
 |
Условие
Алхимик Петя изобрел философский камень, с использованием которого можно проводить некоторое множество алхимических реакций по превращению одних веществ в другие. Масса вещества, которое подвергается превращению, и масса каждого образующегося в результате реакции вещества составляет ровно один грамм. Закон сохранения массы при этом может нарушаться, поскольку Пете он неизвестен.Изначально у Пети имеется один грамм свинца. С помощью философского камня Петя может превратить свой свинец в другие вещества, на которые он потом также сможет воздействовать философским камнем. Выполняя одну за другой алхимические реакции, Петя стремится получить как можно больше золота.
Требуется написать программу, определяющую по заданному описанию
алхимических реакций, выполняемых философским камнем, наибольшее
количество золота, которое может получить Петя.
Входные данные
В первой строке входного файла записано целое число K – количество
различных веществ, участвующих и образующихся в алхимических реакциях
(2 ≤ K ≤ 100). Вторая строка содержит названия этих веществ, разделенные
пробелом (в списке обязательно есть свинец и золото). Названия веществ не
длиннее 10 букв.
В третьей строке записано целое число L – количество типов реакций,
выполняемых философским камнем (1 ≤ L ≤ 100). Далее идут L описаний этих
реакций. Каждое описание реакции состоит из двух строк: первая строка
содержит название вещества, которое подвергается превращению, вторая –
названия веществ, получающихся в результате реакции.
Выходные данные
Ваша программа должна вывести в выходной файл либо одно целое число –
искомое количество граммов золота, либо сообщение «QUANTUM SATIS»
(лат. "Сколько нужно"), если Петя может получить любое наперед заданное количество золота.
Пример входного файла
4
свинец золото рога копыта
3
свинец
золото рога копыта
рога
золото копыта
копыта
золото
Пример выходного файла
4
Решение
Скачать архив тестов и решенийПостроим ориентированный граф G, вершины которого соответствуют заданным веществам, а ребра – возможности получить из одного вещества другое с помощью какой-либо из реакций. Скажем, что из вещества A можно косвенно получить вещество B, если существует такая цепочка реакций, которая из одного грамма A производит какое-то количество B (или, говоря в терминах графа G, существует путь из вершины A в вершину B). Назовем максимумом A максимальное количество грамм вещества А, которое Петя может получить из одного грамма свинца. Если максимум A равен нулю, будем называть вещество A нулевым. Наконец, вещество A будем называть бесконечным, если его максимум неограничен.
Первым делом определим все нулевые и бесконечные вещества. Очевидно,
что нулевыми веществами будут те, которые не могут быть косвенно получены
из свинца. Утверждается, что вещество B может быть бесконечным только в
следующих двух случаях:
1) Существует такое бесконечное A, что B косвенно из него получается.
2) Существует такое ненулевое вещество A, что с помощью одной из
реакций можно получить из него B и еще какие-то B1, ..., Bk
и существует i, такое что из Bi
косвенно получается A.
Таким образом, для нахождения всех нулевых и бесконечных веществ достаточно вычислить матрицу достижимостей графа G [Кристофидес 78, п. 2.2] с помощью рефлексивного транзитивного замыкания его матрицы смежности [Липский 88, п. 3.5].
Если золото оказалось среди нулевых или бесконечных веществ, то ответ на задачу найден. В противном случае выбросим из графа G все вершины, соответствующие таким веществам, и все ребра, им инцидентные. Теперь определим максимум для каждого из оставшихся веществ.
Заметим, что если из вещества A можно косвенно получить вещество B, а из вещества B можно косвенно получить вещество A (или, в терминах графа G, если вершины A и B лежат в одной компоненте сильной связности), то максимумы A и B совпадают. Разобьем все оставшиеся вещества по этому признаку на классы эквивалентности. Построим конденсацию G1 графа G [Кристофидес 78, п. 2.3], вершинами которой эти классы эквивалентности будут являться. При этом мы оставляем в рассмотрении лишь те реакции, которые приводят к получению веществ из других классов, нежели вещество, вступающее в реакцию.
Определим для каждой вершины Ai конденсации G1 максимальное количество золота, которое можно получить из одного грамма Ai , т.е. из одного грамма любого из веществ этого класса. Тогда ответом на исходную задачу будет являться значение для класса, в котором содержится свинец.
Если Ai
– это класс, содержащий золото, то искомое значение равно
единице. В противном случае оно может быть вычислено рекурсивно с
использованием метода динамического программирования. А именно,
перебираем все реакции Rij
, которые можно провести с веществами из класса Ai.
Для каждой реакции Rij
рекурсивно подсчитываем максимальное количество
золота для каждого из веществ, получающегося в результате этой реакции, и
вычисляем сумму этих количеств. Далее выбираем максимальную из найденных
сумм по всем возможным j. Это число и будет искомым значением для класса
Ai.
Упражнение
Докажите утверждение о бесконечном веществе.
