Задача №113515. Боссы
Компания сотрудников должна провести реструктуризацию. В результирующей иерархии, представленной как корневое дерево, каждый узел будет боссом своих детей. Кроме того, всем работникам должна быть назначена зарплата. Зарплата должна быть положительным целым числом, а зарплата каждого босса должна быть больше суммы окладов их непосредственных подчиненных. Ваша задача состоит в том, чтобы структурировать компанию, чтобы все вышеперечисленные условия соблюдались, а сумма всех зарплат была как можно меньше.
Первая строка ввода содержит целое число: количество сотрудников. Сотрудники имеют номера от 1 до n . После этого вход содержит n строк, описывающих предпочтения сотрудников. В i -й строке содержится целое число k i , за которым следует список целых чисел. Список состоит из всех сотрудников, которых i -й работник готов принять в качестве своего босса.
Вы должны получить самую низкую общую зарплату среди всех действительных реструктуризаций. Гарантируется что существует хотя бы одно решение.
подзадача 1(22 балла)
2 < n < 10 k i ≤ 20
подзадача 2(45 балла)
2 <
n
< 100
k
i
≤ 200
подзадача 3(33 балла)
2 <
n
< 5000
k
i
≤ 10000
4 1 4 3 1 3 4 2 1 2 1 3
8