icontofig | 发布于 2019-08-07 22:04:05 | 阅读量 270 | 左偏树
发布于 2019-08-07 22:04:05 | 左偏树

 Description

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

Input

从标准输入读入数据。
第一行包含两个整数 N M,其中 N表示忍者的个数,M表示薪水的总预算。
接下来 N行描述忍者们的上级、薪水以及领导力。其中的第 i 行包含三个整 Bi , C i , L i分别表示第i个忍者的上级,薪水以及领导力。Master满足B i = 0并且每一个忍者的老板的编号一定小于自己的编号 Bi < i

Output

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

Sample Input

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Sample Output

6

数据范围

1  ≤N ≤ 100,000 忍者的个数;
1  ≤M ≤ 1,000,000,000 薪水总预算;  
0  ≤Bi < i  忍者的上级的编号;
1  ≤Ci ≤ M                     忍者的薪水;
1  ≤Li ≤ 1,000,000,000             忍者的领导力水平。

题解

 我们将关系树图建出来,直接dfs,对于每一个点维护一个大根堆、子树中选取忍者的个数,大根堆用左偏树的方法实现合并。

对于当前的管理者,计算其子树的选中的忍者的总共需要的薪水sum,如果sum > m,则删除当前节点对应左偏树的根,并合并左右子树。直到sum <= m,更新答案。

最后全部枚举完,输出答案。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
typedef long long ll;
const int maxn = 1e5+5;
int c[maxn],dis[maxn];
ll d[maxn],siz[maxn];
ll sum[maxn];
int n;
ll m;
ll k[maxn];
int l[maxn],r[maxn];
int f[maxn];
int val[maxn];
int merge(int a,int b){
    if(!a || !b)return a + b;
    if(val[a] < val[b])swap(a,b);
    r[a] = merge(r[a],b);
    if(dis[r[a]] > dis[l[a]])swap(r[a],l[a]);
    dis[a] = dis[r[a]] + 1;
    return a;
}
ll ans = 0;
struct edge{
    int to,next;
}e[maxn];
int h[maxn];
int cnt = 0;
void add(int u,int v){
    e[cnt].next = h[u];e[cnt].to = v;h[u] = cnt++;
    return;
}
int tot = 0;
void dfs(int now){
    f[now] = ++tot;
    val[tot] = c[now];
    siz[now] = 1;
    sum[now] = c[now];
    for(int i = h[now];i != -1;i = e[i].next){
        dfs(e[i].to);
        sum[now] += sum[e[i].to];
        siz[now] += siz[e[i].to];
        f[now] = merge(f[now],f[e[i].to]);
    }
    while(sum[now] > m){
        sum[now] -= val[f[now]];
        siz[now] -= 1;
        int x = l[f[now]],y = r[f[now]];
        f[now] = merge(x,y);
    }
    ans = max(ans,siz[now] * d[now]);
}
int main(){
    memset(h,-1,sizeof(h));
    tot = 0;
    n = get_num();
    for(int i = 1;i <= n;++i)
        f[i] = i;
    m = get_num();
    for(int i = 1;i <= n;++i){
        int a = get_num();
        add(a,i);
        c[i] = get_num();d[i] = get_num();
    }
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}

 


内容更新于: 2019-08-07 22:04:05
链接地址: http://blog.leanote.com/post/icontofig/APIO-2012dispatching

上一篇: 2019 Multi-University Training Contest 6 1005 Snowy Smile 线段树维护最大子段和

下一篇: 2019 Multi-University Training Contest 5 1002 three arrays Trie树+思维题

270 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航