首页 > 代码库 > Bzoj2809 [Apio2012]dispatching
Bzoj2809 [Apio2012]dispatching
Submit: 2937 Solved: 1536
Description
在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作获取报偿。在这个帮派里,有一名忍者被称之为 Master。除了 Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水,同时使得支付的薪水总额不超过你的预算。另外,为了发送指令,你需要选择一名忍者作为管理者,要求这个管理者可以向所有被派遣的忍者 发送指令,在发送指令时,任何忍者(不管是否被派遣)都可以作为消息的传递 人。管理者自己可以被派遣,也可以不被派遣。当然,如果管理者没有被排遣,就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平,其中每个忍者的领导力水平也是一定的。写一个程序,给定每一个忍者 i的上级 Bi,薪水Ci,领导力L i,以及支付给忍者们的薪水总预算 M,输出在预算内满足上述要求时顾客满意度的最大值。
1 ≤N ≤ 100,000 忍者的个数;
1 ≤M ≤ 1,000,000,000 薪水总预算;
0 ≤Bi < i 忍者的上级的编号;
1 ≤Ci ≤ M 忍者的薪水;
1 ≤Li ≤ 1,000,000,000 忍者的领导力水平。
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
左偏树/可并堆
下意识写了并查集,然而并没有什么用。
47行del函数没有传实参,RE了3遍才发现。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mxn=100010;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15 return x*f;16 }17 struct edge{18 int v,nxt;19 }e[mxn<<1];20 int hd[mxn],mct=0;21 void add_edge(int u,int v){22 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;23 }24 struct ninja{int fa;LL c,le;}a[mxn];25 struct node{26 int l,r;27 LL w;28 }t[mxn];29 //30 int n;LL m;31 //可并堆 32 int fa[mxn],rt[mxn],size[mxn],cnt;33 LL sum[mxn];34 int find(int x){35 if(fa[x]==x)return x;36 return fa[x]=find(fa[x]);37 }38 int dep[mxn];39 int mge(int x,int y){40 if(x*y==0)return x+y;41 if(t[x].w<t[y].w){swap(x,y);}//大根堆42 t[x].r=mge(t[x].r,y);43 if(dep[t[x].l]<dep[t[x].r])swap(t[x].l,t[x].r);44 dep[x]=dep[t[x].r]+1;45 return x;46 }47 void del(int &x){//48 x=mge(t[x].l,t[x].r);49 // fa[fa[x]]=fa[x];50 return;51 }52 inline LL top(int x){53 // int x=find(x);54 return t[x].w;55 }56 //57 LL ans=0;58 void DFS(int u){59 rt[u]=++cnt;60 t[cnt].w=a[u].c;61 sum[u]=a[u].c;62 size[u]=1;63 for(int i=hd[u];i;i=e[i].nxt){64 int v=e[i].v;65 DFS(v);66 sum[u]+=sum[v];67 size[u]+=size[v];68 rt[u]=mge(rt[u],rt[v]);69 }70 while(sum[u]>m){//维护堆中sum小于M 71 sum[u]-=top(rt[u]);72 del(rt[u]);size[u]--;73 }74 ans=max(ans,(LL)size[u]*a[u].le);75 return;76 }77 int main(){78 int i,j;79 n=read();m=read();80 for(i=1;i<=n;i++){81 a[i].fa=read();82 a[i].c=read();83 a[i].le=read();84 add_edge(a[i].fa,i);85 }86 DFS(1);87 printf("%lld\n",ans);88 return 0;89 }
Bzoj2809 [Apio2012]dispatching
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。