BZOJ2809——[Apio2012]dispatching

1、题目大意：给一棵树和M值，每个点有两个权值C和L，选x个点，这x个点的C值的和不能超过M，且这x个点如果都在某个子树内

定义满意度为x*这个子树的根的L值

2、分析：这是一道可并堆的题目，我们考虑每一个子树，我们想让其中的选的点尽量多但是C和却不超过M

我们只需取C值最小的，次小的，第三小的……直到不能选为止，这个不是很简单吗，不就是一个堆吗

不对，难道对于每一个子树都要建一个堆吗，那不是爆了吗，我们只需把这个子树的所有子节点所在的堆全都合并

还要再加上这个子树的根节点，这样就可以了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000000
#define LL long long
struct merge_heap{
    int l[M], r[M], d[M], value[M];
    void init(){
        memset(l, 0, sizeof(r));
        memset(r, 0, sizeof(r));
        memset(d, 1, sizeof(d));
    }
    int merge(int x, int y){
        if(!x) return y;
        if(!y) return x;
        if(value[x] < value[y]) swap(x, y);
        r[x] = merge(r[x], y);
        if(d[l[x]] < d[r[x]]){
            swap(l[x], r[x]);
        }
        d[x] = d[l[x]] + 1;
        return x;
    }
} wt;
int n, m;
int C[M], L[M];
int head[M], Next[M], son[M], tot;
int tree[M];
int sum[M], size[M];
LL ans = 0;
void dfs(int x){
    for(int i = head[x]; i != -1; i = Next[i]){
        dfs(son[i]);
        sum[x] += sum[son[i]];
        size[x] += size[son[i]];
        tree[x] = wt.merge(tree[x], tree[son[i]]);
        while(sum[x] > m){
            size[x] --;
            sum[x] -= wt.value[tree[x]];
            tree[x] = wt.merge(wt.l[tree[x]], wt.r[tree[x]]);
        }
    }
    ans = max((LL)L[x] * (LL)size[x], ans);
}
int main(){
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        int fa;
        scanf("%d%d%d", &fa, &C[i], &L[i]);
        wt.value[i] = C[i];
        Next[++ tot] = head[fa];
        head[fa] = tot;
        son[tot] = i;
        sum[i] = C[i];
        size[i] = 1;
    }
    wt.init();
    for(int i = 1; i <= n; i ++) tree[i] = i;
    dfs(0);
    printf("%lld\n", ans);
    return 0;
}

巴特西

BZOJ2809——[Apio2012]dispatching

最新文章

热门文章