|
Название задачи: Взлом сети . |
 |
Условие
Компьютерная сеть Пентагона состоит из N компьютеров, некоторые из которых соединены прямыми двусторонними каналами связи. В целях повышения секретности при проектировании сети количество каналов связи было сокращено до минимума с тем условием, чтобы любые два компьютера имели возможность обмена информацией либо непосредственно, либо через другие компьютеры сети.
КГБ хочет прослушивать все передаваемые в сети Пентагона сообщения.
Для этого советскими программистами был разработан вирус, который, будучи
установлен на какой-либо из компьютеров, передает КГБ всю информацию,
проходящую через него. Оказалось, что материальные затраты, необходимые
для установки вируса на различные компьютеры, различны. Требуется
определить набор компьютеров, которые КГБ должно инфицировать, чтобы
минимизировать общие материальные затраты.
Входные данные
Первая строка входного файла содержит N – количество компьютеров в сети
(1 ≤ N ≤ 500). В i-й из последующих N строк содержатся номера компьютеров,
с которыми непосредственно связан компьютер номер i. Далее следуют N целых
чисел из диапазона [1, 1000] – материальные затраты, связанные с установкой
вируса на каждый из компьютеров.
Выходные данные
В выходной файл выведите минимально возможные суммарные затраты и
список номеров компьютеров, которые нужно инфицировать, упорядоченный
по возрастанию.
Пример входного файла
5
5
4
4
2 3 5
4 1
1 5 5 2 10
Пример выходного файла
3
1 4
Решение
Скачать архив тестов и решений
Первый абзац условия задачи в результате формализации сводится к словам
«задано дерево с N вершинами», второй – «найти доминирующее над ребрами
множество вершин минимального веса». Выберем какую-нибудь вершину
заданного дерева в качестве корня и подвесим дерево за эту вершину. Для
каждого поддерева определим пару чисел (a, b), где a равняется ответу на нашу
задачу для этого поддерева, а b – ответом на ту же задачу с дополнительным
требованием включения корня рассматриваемого поддерева в искомое
множество.
Эти пары чисел (a, b) вычисляются динамически по высоте поддеревьев.
Для дерева, состоящего из единственной вершины, a равно нулю, a b – весу
этой вершины. Теперь покажем, как вычислить числа a, b для дерева,
состоящего из большего числа вершин. Его корень имеет какое-то количество
поддеревьев, для которых пары чисел (ai
, bi
) уже подсчитаны. Ясно, что число b равно сумме всех чисел ai
, увеличенной на вес корня рассматриваемого дерева.
Число a, в свою очередь, равно минимуму из суммы чисел bi
и числа b.
Описанная процедура легко реализуется рекурсивным алгоритмом.
Упражнение
Решите аналогичную задачу для случая, когда нужно контролировать не каналы
связи, а деятельность компьютеров, причем контролировать деятельность
компьютера вирус может либо находясь на этом компьютере, либо с любого из
соседних компьютеров.
