APIO2012 派遣

题目背景

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。

题目描述

在这个帮派里，有一名忍者被称之为Master。除了Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。

现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。

你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。

写一个程序，给定每一个忍者i的上级Bi，薪水Ci，领导力Li，以及支付给忍者们的薪水总预算M，输出在预算内满足上述要求时顾客满意度的最大值。

输入输出格式

输入格式：

第一行包含两个整数N和M，其中N表示忍者的个数，M表示薪水的总预算。

接下来N行描述忍者们的上级、薪水以及领导力。其中的第i行包含三个整数Bi,Ci,Li分别表示第i个忍者的上级，薪水以及领导力。Master满足Bi=0，并且每一个忍者的老板的编号一定小于自己的编号Bi<i。

输出格式：

输出一个数，表示在预算内顾客的满意度的最大值。

输入输出样例

输入样例#1：

5 4

0 3 3

1 3 5

2 2 2

1 2 4

2 3 1

输出样例#1：

6

说明

\(1 ≤ N ≤ 100,000\) 忍者的个数；

\(1 ≤ M ≤ 1,000,000,000\) 薪水总预算；

\(0 ≤ Bi < i\) 忍者的上级的编号；

\(1 ≤ Ci ≤ M\) 忍者的薪水；

\(1 ≤ Li ≤ 1,000,000,000\) 忍者的领导力水平。

对于 30%的数据，\(N ≤ 3000。\)

Solution

---

观察数据,因为保证master的上级是0,而所有忍者又有且仅有一个上级,所以可以保证数据是树形结构,要求在M的预算内使得满意度尽可能高,其中满意度定义为

一个领导者的领导力*它能派遣的忍者,我们发现对于每一棵子树,我们都可以以它为根进行处理,在自下而上回溯更新答案

所以,30分应该是可以用树上背包做的

---

那么正解呢?

左偏树!!!!

利用左偏树自下而上维护答案,我们的左偏树除了几本的ls,rs,val外(左儿子,右儿子,节点权值),还维护两个值sum,size,其中sum代表以u为根的子树中所派遣的忍者的总花费,size表示以u为根的子树中所派遣的忍者的数量

---

所以,在dfs中每次赋一个初始值,然后像树形dp一样,在回溯之后在更新,用一个辅助数组rt[u]表示u在左偏树中的根节点,对于一个点对(u,v)(u,v之间有连边),我们在回溯之后合并(rt[u],rt[v]),而在更新所有与u相连的点v∈{son[u]}之后,我们以一种贪心的思想,看当前所选的点的权值是否大于题目所给的预算m,如果大于就把堆顶弹出

---

那么是维护大根堆还是小根堆呢?因为我们要判断当前节点的花费是否大于m,所以为了比较方便,我们维护一个大根堆,即不满足条件就把堆顶弹出,合并左右儿子节点,这里的删除操作因为不需要保存删除节点的信息,所以直接合并儿子节点即可

lol del(lol u){return merge(t[u].ls,t[u].rs);}

---

Code

#include
    
     #define Max(a,b) (a)>(b)?(a):(b)using namespace std;typedef long long lol;const lol N=1e5+10;void in(lol &ans){    ans=0;lol f=1; char i=getchar();    while(i<'0'||i>'9'){if(i=='-') f=-1; i=getchar();}    while(i>='0'&&i<='9') ans=(ans<<3)+(ans<<1)+i-'0',i=getchar();    ans*=f;}lol n,m,cnt,ans;struct Tree{    lol ls,rs,dep,size;    lol val,sum;}t[N];lol to[N<<1],nex[N<<1],head[N],rt[N];lol c[N],l[N];inline void add(lol a,lol b){    to[++cnt]=b,    nex[cnt]=head[a],    head[a]=cnt;}lol merge(lol x,lol y){    if(!x||!y) return x+y;    if(t[y].val>t[x].val || (t[x].val==t[y].val && x
     
      m && t[rt[u]].size)    rt[u]=del(rt[u]);    ans=Max(ans,t[rt[u]].size*l[u]);}int main(){    in(n),in(m); lol x;    for(int i=1;i<=n;i++)    in(x),in(c[i]),in(l[i]),add(x,i),add(i,x);    dfs(1,0); printf("%lld\n",ans);    return 0;}
     
    

博主蒟蒻,随意转载.但必须附上原文链接