BZOJ 5182 [Baltic2016]Bosses


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

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


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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 5182 [Baltic2016]Bosses


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: