题解 P1552 【[APIO2012]派遣】

· · 题解

左偏树裸题。

明显领导关系形成一棵树，则答案为ans=max{L[u]\times k}，其中k代表以u为根的字数中选出的节点数个数（设这些节点为v_1,v_2\cdots v_k）且有\sum_{i=1}^{k}C[v_i]\leq M。

所以以每个节点建一个大根堆，维护薪水值。初始时若自己满足条件就选自己，否则不选。从叶子节点往上推，对于每个节点，将它与它的儿子节点合并。如果当前的选择费用超出了M，就弹出堆里最大的，一直到不超过M为止。动态维护当前选择的节点数num和选择费用sum即可。复杂度有点难分析，不过大概是O(nlogn)级别？如果有大神知道请教我orz

代码：

#include<cstdio>
#include<cstring>
typedef long long ll;
const int maxn=100005,maxe=100005;
int val[maxn],lc[maxn],rc[maxn],dis[maxn],root[maxn],l[maxn],num[maxn],c[maxn],head[maxn],next[maxe],to[maxe],sum[maxn],n,m,cnt,b,w;
ll ans;
void swap(int&a,int&b){int c=a;a=b,b=c;}
int merge(int x,int y)
{
    if(!x||!y)return x?x:y;
    if(val[x]<val[y])swap(x,y);
    rc[x]=merge(rc[x],y);
    if(!lc[x]||dis[lc[x]]<dis[rc[x]])swap(lc[x],rc[x]);
    dis[x]=dis[rc[x]]+1;
    return x;
}
void insert(int a,int b){to[cnt]=b,next[cnt]=head[a];head[a]=cnt++;}
ll max(ll a,ll b){return a>b?a:b;}
int main()
{
    memset(head,-1,sizeof head);dis[0]=-1;
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&b,c+i,l+i);
        insert(b,i);
    }
    for(register int u=n;u;--u)
    {
        if(c[u]<=m)root[u]=++w,num[u]=1,val[w]=sum[u]=c[u];
        for(register int i=head[u],v=to[i];~i;v=to[i=next[i]])
        {
            root[u]=merge(root[u],root[v]);
            sum[u]+=sum[v],num[u]+=num[v];
            while(sum[u]>m)
            {
                sum[u]-=val[root[u]];--num[u];
                root[u]=merge(lc[root[u]],rc[root[u]]);
            }
        }
        ans=max(ans,(ll)l[u]*num[u]);
    }
    printf("%lld\n",ans);
    return 0;
}