不知左偏树为何物的同学,请先参考黄源河大牛在2005年的论文。
【题目描述】
在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作 获取报偿。
在这个帮派里,有一名忍者被称之为 Master 。除了Master 以外,每名忍者 都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关 的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。
现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水,同时使得支付的薪水总额不超过你的预算。另外,为了发送指 令,你需要选择一名忍者作为管理者,要求这个管理者可以向所有被派遣的忍者 发送指令,在发送指令时,任何忍者(不管是否被派遣)都可以作为消息的传递 人。管理者自己可以被派遣,也可以不被派遣。当然,如果管理者没有被排遣, 你就不需要支付管理者的薪水。
你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的 忍者总数乘以管理者的领导力水平,其中每个忍者的领导力水平也是一定的。
写一个程序,给定每一个忍者i 的上级B ,薪水C ,领导力L ,以及支付给 忍者们的薪水总预算M ,输出在预算内满足上述要求时顾客满意度的最大值。
【数据范围】
1 ≤ N ≤ 100,000 忍者的个数;
1 ≤ M ≤ 1,000,000,000 薪水总预算;
0 ≤ B < i 忍者的上级的编号;
1 ≤ C ≤ M 忍者的薪水;
1 ≤ L ≤ 1,000,000,000 忍者的领导力水平。
【输入格式】
从标准输入读入数据。
第一行包含两个整数N 和M ,其中N 表示忍者的个数,M 表示薪水的总预 算。
接下来N 行描述忍者们的上级、薪水以及领导力。其中的第i 行包含三个整 数B , C , L 分别表示第i 个忍者的上级,薪水以及领导力。Master 满足B = 0, 并且每一个忍者的老板的编号一定小于自己的编号 B < i
【思路】
这道题目的难点就是要求出对于每棵子树,在总费用不超过m的情况下,最多能派遣多少忍者。
一般的做法是利用平衡树,在nlog(n)的时间内求解。
这里讨论的是如何利用左偏树来维护最大的忍者数目。
首先,假设一个节点所有的子树要派遣的忍者都已经求出,且存放在左偏树里现在要通过子节点来求出根对应的左偏树。
显而易见的是,根所选择的忍者一定在其子树所选的忍者中。如果把子树都加进去还没有超过m,那么答案已经求出来了。如果超过了m那么就应该贪心地一直删去价格最大的忍者,直到总价格在m内为止。这种操作可以用左偏树来维护。
下面直接上代码。
program dispatching; type int=longint; var i,j,k,m,n:int; l,r,p,c:array[0..100500]of int64;//p是价格;c是lead值 ls,rs,sp,sc,dis:array[-1..100500]of int64;//sp是子树节点的p值之和;sc是子树中的节点数 x,y,z:int; max:int64; function swap(var x,y:int64):int; var t:int64; begin t:=x;x:=y;y:=t; end; function union(x,y:int64):int; begin if(x=-1)or(y=-1)then exit(-x*y); if p[x]<p[y]then swap(x,y); rs[x]:=union(rs[x],y); if dis[rs[x]]>dis[ls[x]]then swap(ls[x],rs[x]); dis[x]:=dis[rs[x]]+1; sp[x]:=sp[rs[x]]+sp[ls[x]]+p[x]; sc[x]:=sc[ls[x]]+sc[rs[x]]+1; exit(x); end; function delete(rt:int):int; begin while sp[rt]>m do rt:=union(ls[rt],rs[rt]); exit(rt); end; function bfs(rt:int):int; var i,j,root:int; begin root:=rt; ls[rt]:=-1;rs[rt]:=-1; sp[rt]:=p[rt];sc[rt]:=1; dis[rt]:=dis[rs[rt]]+1; j:=l[rt]; while j<>-1 do begin i:=bfs(j); rt:=union(rt,i); rt:=delete(rt); j:=r[j]; end; if sc[rt]*c[root]>max then max:=sc[rt]*c[root]; exit(rt); end; begin assign(input,'dispatching.in');reset(input); assign(output,'dispatching.out');rewrite(output); fillchar(l,sizeof(l),$FF); read(n,m); for i:=1 to n do begin read(x); r[i]:=l[x];l[x]:=i; read(p[i],c[i]); end; max:=0;dis[-1]:=0; sc[-1]:=0;sp[-1]:=0; bfs(l[0]); write(max); close(input); close(output); end.
BY QW
转载请注明出处