Компьютерная сеть Пентагона состоит из 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

   Решение

Докажите, что если точка пересечения высот остроугольного треугольника делит высоты в одном и том же отношении, то треугольник правильный.

   Решение

Страница: 1 2 >> [Всего задач: 7]      

Окружность делит каждую из сторон треугольника на три равные части. Докажите, что этот треугольник правильный.

Прислать комментарий

Решение

Из точки M, лежащей внутри правильного треугольника ABC, опущены перпендикуляры MP, MQ и MR на стороны AB, BC и CA соответственно. Докажите, что  AP² + BQ² + CR² = PB² + QC² + RA² и  AP + BQ + CR = PB + QC + RA.

Прислать комментарий

Решение

Точки D и E делят стороны AC и AB правильного треугольника ABC в отношениях  AD : DC = BE : EA = 1 : 2. Прямые BD и CE пересекаются в точке O. Докажите, что  AOC = 90^o.

Прислать комментарий

Решение

Докажите, что если точка пересечения высот остроугольного треугольника делит высоты в одном и том же отношении, то треугольник правильный.

Прислать комментарий

Решение

а) Докажите, что если  a + h_a = b + h_b = c + h_c, то треугольник ABC правильный.
б) В треугольник ABC вписаны три квадрата: у одного две вершины лежат на стороне AC, у другого — на BC, у третьего — на AB. Докажите, что если все три квадрата равны, то треугольник ABC правильный.

Прислать комментарий

Решение

Страница: 1 2 >> [Всего задач: 7]