BZOJ 5182 [Baltic2016]Bosses

发布于 2018-03-14  79 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5182

题意:公司里面 n 名员工将要被改组。经过调整后的公司人员结构将为树状结构,而每个节点的人将成为其所有子节点的上司。然而,每个员工都有他能接受的上司人选,改组必须满足他们的要求。除此之外,公司要给每个员工支付薪水(这一数额为正整数),并且上司的薪水需要比其所有直系下属的薪水总和都多。现在你的任务便是要合理安排这一人员结构,并使公司支付的薪水总和尽可能少。


如果确定了树的结构,答案即每个节点的深度和,因为叶子节点肯定是 1,相当于一条链加一。

深度和最小以每个点为根求一下 bfs 生成树即可,注意树是有向的,判不存在的情况。

 


一个非常弱的准退役OIER