bzoj 2809: [Apio2012]dispatching

Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者 发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递 人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者

 i的上级

 B

i

，薪水

Ci

，领导力

L i

，以及支付给忍者们的薪水总预算

 M，输出在预算内满足上述要求时顾客满意度的最大值。

 

1  ≤

N ≤ 100,000 忍者的个数；

1  ≤

M ≤ 1,000,000,000 薪水总预算； 

 

0  ≤

B

i < i  忍者的上级的编号；

1  ≤

C

i ≤ M                     忍者的薪水；

1  ≤

L

i ≤ 1,000,000,000             忍者的领导力水平。

Input

从标准输入读入数据。

 

第一行包含两个整数

 N和

 M，其中

 N表示忍者的个数，

M表示薪水的总预算。

 

接下来

 N行描述忍者们的上级、薪水以及领导力。其中的第

 i 行包含三个整 

B

i , C i , L i

分别表示第

i

个忍者的上级，薪水以及领导力。

Master

满足

B i = 0

，并且每一个忍者的老板的编号一定小于自己的编号 

B

i < i

。

Output

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

Sample Input

5 4

0 3 3

1 3 5

2 2 2

1 2 4

2 3 1

Sample Output

6

HINT

如果我们选择编号为 1的忍者作为管理者并且派遣第三个和第四个忍者，薪水总和为 4，没有超过总预算。

因为派遣了2 个忍者并且管理者的领导力为 3，用户的满意度为 6  ，是可以得到的用户满意度的最大值。

题目剖析：

ans=领导力*个数

领导力：枚举每个忍者

个数：当然是需要薪水少的先派遣啦

所以，节点的领导力为a，在以这个节点为根的子树中（包括这个节点），从小到大选尽可能多的节点s，满足节点的薪水和<=总预算，最大化a*s

这道题还可以用左偏树来做，但蒟蒻一枚只会主席树 ，所以这里只写主席树做法

推荐黄学长的博客，维护子树大根堆，用可并堆将时间复杂度降为nlongn

数据结构：主席树

辅助：dfs序（开始没想到）

以忍者的dfs序为下标，薪水为区间建立主席树

首先说说dfs序

1、为什么需要dfs序？

因为派遣忍者的范围是以这个忍者为根的子树。

假设当前节点为i，遍历到时令 in[i]=a， 表示i是第a个被遍历。以i为节点的子树遍历完后，令out[i]=b,b为当前所有已遍历节点总数

那么这个节点可以派遣的范围是dfs序[a,b]（包括a，b）之间的忍者

所dfs序的作用是锁定查找区间

2、如何构造dfs序？（自己也没想到）

令t表示当前已遍历节点总数，每遍历一个节点t++，设当前节点为i，遍历到i是in[i]=t，i退出时out[i]=t

在构造dfs序时，顺便记录下dfs序为i的忍者的薪水、领导力，然后按照dfs序在主席树中插入节点

最后是查找

枚举每个忍者，查找他的派遣范围最多能派遣多少个忍者

如果做过，会知道那道题在查询查到叶子节点时，对答案的贡献是sum[l]/count[l]*k

本题查询的是数量，到叶子节点时有没有坑呢？

有。叶子节点对答案有贡献的忍者数量应该是 min(薪水预算/派遣这个节点的忍者所需薪水，这个节点的忍者个数)

这里的节点是主席树中以薪水为区间建立的节点

还有就是要注意答案用long long

#include
      
       #include
       
        #define N 100001using namespace std;int n,m,money[N],lead[N],front[N],next[N];int hash[N],cnt_money;int in[N],out[N],t;int root[N],tot,lc[N*20],rc[N*20],cnt[N*20];long long sum[N*20],ans,dispatch;struct node{    int mon,lea;}e[N];inline void add(int u,int v){    next[v]=front[u];    front[u]=v;}inline int dfs(int r){    in[r]=++t;    e[t].lea=lead[r];e[t].mon=hash[r];    if(front[r])        for(int i=front[r];i;i=next[i])            dfs(i);    out[r]=t;}void discrete(){    sort(money+1,money+n+1);        cnt_money=unique(money+1,money+n+1)-(money+1);    for(int i=1;i<=n;i++) hash[i]=lower_bound(money+1,money+cnt_money+1,hash[i])-money;}inline void insert(int pre,int & now,int l,int r,int w){    sum[now=++tot]=sum[pre]+money[w];    cnt[now]=cnt[pre]+1;    if(l==r) return;    int mid=l+r>>1;    if(w<=mid)    {        rc[now]=rc[pre];        insert(lc[pre],lc[now],l,mid,w);    }    else    {        lc[now]=lc[pre];        insert(rc[pre],rc[now],mid+1,r,w);    }}inline int query(int x,int y,int l,int r,long long k){    if(l==r) return min(k/(long long)money[l],(long long)(cnt[y]-cnt[x]));    int mid=l+r>>1;    long long tmp=sum[lc[y]]-sum[lc[x]];    if(k<=tmp) return query(lc[x],lc[y],l,mid,k);    else return cnt[lc[y]]-cnt[lc[x]]+query(rc[x],rc[y],mid+1,r,k-tmp);}int main(){    scanf("%d%lld",&n,&m);    int b,c,l;    for(int i=1;i<=n;i++)    {        scanf("%d%d%d",&b,&money[i],&lead[i]);        hash[i]=money[i];        add(b,i);    }    discrete();    dfs(front[0]);    for(int i=1;i<=n;i++) insert(root[i-1],root[i],1,cnt_money,e[i].mon);     for(int i=1;i<=n;i++)    {        int l=in[i],r=out[i];//l：节点i的dfs序，r节点i可以派遣的最靠后的忍者的dfs序         dispatch=query(root[l-1],root[r],1,cnt_money,m);        ans=max(ans,(long long)lead[i]*dispatch);    }    printf("%lld",ans);}
       
      

这道题做的时候

1、没有想到用dfs序锁定查找区间

2、ans=max(忍者的领导力*派遣忍者个数)，没有想到可以枚举每个忍者，这样就解决了领导力的问题。对答案的分解能力欠缺

3、答案没用long long，开始做的时候还想着答案用long long，想先写出来过了样例后再改，结果忘了

4、查询时，如果当前区间为[x,y]，要到节点的右孩子去查询，返回的答案应是区间左右端点左孩子的cnt差，而不是y的cnt。这里与任务查询系统混了，因为任务查询系统查询的区间是[0,y]，0可以省略，所以可以直接用y的cnt、sum