[BZOJ 2809] Dispatching

Link:https://www.lydsy.com/JudgeOnline/problem.php?id=2809

Algorithm:

很容易看出此题贪心的思路：

只要在每个点的子树中贪心选取费用最小的，使其总和不超过m即可

维护最小值，想到用堆，但普通的堆无法进行合并

于是用到数据结构可并堆/左偏树来在O（logN）的时间内合并堆

可并堆和左偏树的区别仅仅在于左偏树多维护了dist数组，而可并堆是无脑交换左右子树

这也使得左偏树的复杂度是能证明的O（logN），而可并堆仅仅是均摊复杂度为O（logN），因此还是尽量用左偏树吧

证明：n个节点的左偏树的距离dist最大为log(n+1)-1

若左偏树的距离为一定值，则节点数最少的左偏树是完全二叉树。

设一棵左偏树的距离为k，则这棵左偏树至少有2^{k+1}-1个节点。

因为n>=2^{k+1}-1，所以k<=log(n+1)-1

Code:

左偏树：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read()

{

    char ch;int num,f=;

    while(!isdigit(ch=getchar())) f|=(ch=='-');

    num=ch-'';

    while(isdigit(ch=getchar())) num=num*+ch-'';

    return f?-num:num;

}

const int MAXN=1e5+;

vector<int> G[MAXN];

struct LTree

{

    int ls,rs,dist,val;

    ll siz,sum;

}Lt[MAXN];

int n,m,C[MAXN],L[MAXN],root[MAXN];

ll res=;

int merge(int x,int y)

{

    if(!x || !y) return x+y;

    if(Lt[x].val<Lt[y].val) swap(x,y);

    Lt[x].rs=merge(Lt[x].rs,y);

    if(Lt[Lt[x].ls].dist<Lt[Lt[x].rs].dist) swap(Lt[x].ls,Lt[x].rs);

    Lt[x].dist=Lt[Lt[x].rs].dist+;

    Lt[x].siz=Lt[Lt[x].rs].siz+Lt[Lt[x].ls].siz+;

    Lt[x].sum=Lt[Lt[x].rs].sum+Lt[Lt[x].ls].sum+Lt[x].val;

    return x;

}

void pop(int &x)

{

    x=merge(Lt[x].ls,Lt[x].rs);

}

void dfs(int x)

{

    root[x]=x;

    for(int i=;i<G[x].size();i++)

        dfs(G[x][i]),root[x]=merge(root[x],root[G[x][i]]);

    while(Lt[root[x]].siz && Lt[root[x]].sum>m) pop(root[x]);

    res=max(res,L[x]*Lt[root[x]].siz);

}

int main()

{

    n=read();m=read();

    for(int i=;i<=n;i++)

    {

        int x=read();G[x].push_back(i);

        C[i]=read();L[i]=read();

        Lt[i].sum=Lt[i].val=C[i];Lt[i].siz=;

    }

    dfs();

    cout << res;

    return ;

}

可并堆：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read()

{

    char ch;int num,f=;

    while(!isdigit(ch=getchar())) f|=(ch=='-');

    num=ch-'';

    while(isdigit(ch=getchar())) num=num*+ch-'';

    return f?-num:num;

}

const int MAXN=1e5+;

vector<int> G[MAXN];

int n,m,C[MAXN],L[MAXN],root[MAXN];

ll res=;

struct SkewHeap

{

    int v[MAXN],ls[MAXN],rs[MAXN];

    ll siz[MAXN],sum[MAXN];

    int merge(int x,int y)

    {

        if(!x || !y) return x+y;

        if(v[x]<v[y]) swap(x,y);

        rs[x]=merge(rs[x],y);

        swap(ls[x],rs[x]);

        sum[x]=sum[ls[x]]+sum[rs[x]]+v[x];

        siz[x]=siz[ls[x]]+siz[rs[x]]+;

        return x;

    }

    void pop(int &x){x=merge(ls[x],rs[x]);}

}Heap;

void dfs(int x)

{

    root[x]=x;

    for(int i=;i<G[x].size();i++)

        dfs(G[x][i]),root[x]=Heap.merge(root[x],root[G[x][i]]);

    while(Heap.siz[root[x]] && Heap.sum[root[x]]>m) Heap.pop(root[x]);

    res=max(res,L[x]*Heap.siz[root[x]]);

}

int main()

{

    n=read();m=read();

    for(int i=;i<=n;i++)

    {

        int x=read();G[x].push_back(i);

        C[i]=read();L[i]=read();

        Heap.siz[i]=;Heap.sum[i]=Heap.v[i]=C[i];

    }

    dfs();

    cout << res;

    return ;

}

Review:

1、对于每棵左偏树，最好用root[x]记录其根节点

2、对于左偏树要跟着维护的信息，

在merge的最后进行更新

3、可选择将整个数据结构封装在一个类中，写起来可能方便点

logn

[BZOJ 2809] Dispatching