[2018.12.6]BZOJ2809 [Apio2012]dispatching

川长思鸟来 2022-01-09 05:37 262阅读 0赞

考虑维护每一个点以及它的子树中被派遣的忍者。

对于一个点,我们用类似树形DP的方式自底向上进行,先把它的所有孩子中被派遣的忍者放到一起,如果他们的薪水总和超过\\(m\\),就不停地将其中薪水最大的忍者删除,直到薪水总和小于等于\\(m\\)。

找到所有点中领导能力和被派遣忍者数量乘积的最大值即可。

即维护数据结构,支持合并,删除和求最大值。

就是维护可并堆。

可以使用左偏树。

[左偏树][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    struct Ltree{
        int v,d,f,c[2];
    }t[100010];
    int n,m,b[100010],c[100010],l[100010],f[100010];
    long long ans,num[100010],sum[100010];
    vector<int>e[100010];
    int Merge(int &x,int &y){
        if(!y)return x;
        if(!x){
            swap(x,y);
            return x;
        }
        if(t[x].v<t[y].v)swap(x,y);
        Merge(t[x].c[1],y);
        t[t[x].c[1]].f=x;
        if(t[t[x].c[0]].d<t[t[x].c[1]].d)swap(t[x].c[0],t[x].c[1]);
        t[x].d=t[t[x].c[1]].d+1;
        return x;
    }
    int Delete(int x){
        t[t[x].c[0]].f=t[t[x].c[1]].f=0;
        return Merge(t[x].c[0],t[x].c[1]);
    }
    void TDP(int x){
        for(int i=0;i<e[x].size();i++){
            if(e[x][i]!=b[x]){
                TDP(e[x][i]);
                if(f[e[x][i]]){
                    num[x]+=num[e[x][i]];
                    sum[x]+=sum[e[x][i]];
                    f[x]=Merge(f[x],f[e[x][i]]);
                }
            }
        }
        while(sum[x]>m){
            sum[x]-=t[f[x]].v;
            num[x]--;
            f[x]=Delete(f[x]);
        }
        ans=max(ans,num[x]*l[x]);
    }
    int main(){
        scanf("%d%d",&n,&m);
        t[0].d=-1;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&b[i],&c[i],&l[i]);
            f[i]=i;
            e[b[i]].push_back(i);
            t[i].v=c[i];
            t[i].d=0;
            num[i]=1;
            sum[i]=c[i];
        }
        TDP(1);
        printf("%lld",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ2809.html

[Link 1]: https://www.cnblogs.com/xryjr233/p/10536872.html