На сайте acmp.ru появились 300 новых задач, и сейчас самое время их решить.
Это предпоследняя задача регионального этапа Всероссийской олимпиады школьников по информатике 2010 года, то есть уровень сложности выше среднего, но 48% кажутся сильно преувеличенными.
Для тех, кто знаком с алгоритмами на графах, задача не представляет трудности и решается топологической сортировкой, которую проще всего реализовать с помощью поиска в глубину (dfs).
Но давайте рассуждать так, как будто не знаем ничего про графы. Нам необходимо произвести деталь 1, а для этого необходимо произвести все детали, от которых она зависит (которые ещё не произведены). На лицо рекурсия: для решения задачи надо решить такую же подзадачу, только с другим (обычно меньшим) параметром.
Определимся с форматами хранения данных:
- p[i] - время производства детали i,
- used[i] - флаг "произведена ли деталь i?",
- g[i] - список деталей, от которых зависит деталь i,
- result - список деталей для производства в нужном порядке.
Определим нашу рекурсивную функцию таким образом, чтобы она возвращала время производства детали и всех её зависимостей.
Функция довольно простая и делает ровно то, что мы описали словами: сначала проходим по всем зависимостям и если текущая деталь ещё не изготовлена, то вызываем саму себя от этой детали (тем самым изготовив эту деталь и все её зависимости); в r накапливаем время изготовления. После этого помечаем деталь v готовой, прибавляем время её изготовления и добавляем её в ответ (порядок будет корректным, потому что все зависимости уже добавлены).
А основная программа будет состоять из считывания данных, вызова dfs от первой детали и вывода ответа:
Вот и всё решение. А если вы не знакомы с алгоритмами на графах и вам было довольно сложно, то рекомендую начать их изучать, там всё просто.
Предыдущий выпуск: Задача 7. Золото племени АББА
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
