版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [BalticOI 2016 day1] [Luogu P4674] [LOJ 2780] Bosses" categories:
题目链接
<!-- more -->A company of $n$ employees is due for a restructuring. In the resulting hierarchy,represented as a rooted tree, every node will be the boss of its children.
Each employee has a list of bosses they will accept. In addition, all employees mustbe assigned a salary. The salary must be a positive integer, and the salary of eachboss must be larger than the sum of salaries of their immediate subordinates.
Your task is to structure the company so that all above conditions hold, and the sumof all the salaries is as small as possible.
The first input line contains an integer $n$ : the number of employees. The employees are numbered $1,2,...,n$
.After this, the input contains $n$ lines that describe the preferences of the employees.The $i$th such line contains an integer $k_i$ , followed by a list of $k_i$ integers. The list consists of all employees that the $i$th employee accepts as their boss.
You should output the lowest total salary among all valid restructurings. You can assume that at least one solution exists.
4
1 4
3 1 3 4
2 1 2
1 3
8
$2\leq n \leq 10$
$\sum^n_{i=1}k_i\leq 20$
$2\leq n \leq 100$
$\sum^n_{i=1}k_i\leq 200$
$2\leq n \leq 5000$
$\sum^n_{i=1}k_i\leq 10000$
构造一棵带点权的树, 要求父结点权值不小于子结点权值和, 且所有点权均为正, 问合法的树的最小点权和
对于一棵合法的树, 不难发现最小点权和即为所有点深度的和
所以我们应该让构造的树深度尽可能小, 那么很自然就可以想到 BFS
$O(n\sum k_i)$