[BZOJ2809][Apio2012]dispatching 贪心+可并堆
标签：ems problem ring har font cst mem getc family
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2809
我们考虑以每一个节点作为管理者所得的最优答案，一定是优先选择所要薪水少的忍者。那么首先整棵子树的忍者都选上，如果总和大于$M$，那么就不断删除薪水最大的那一个忍者。
然后考虑从下至上合并节点，我们需要一个支持合并的数据结构，就想到了启发式合并平衡树或者可并堆。
可并堆基本原理是维护一个$dis$，表示从根节点到达叶子节点的最短距离，要求$dis[lch]>=dis[rch]$。
1 #include 2 #include 3 #include
4 using namespace std;
5 typedef long long ll;
6 int inline readint(){
7 int Num;char ch;
8 while((ch=getchar())‘0‘||ch>‘9‘);Num=ch-‘0‘;
9 while((ch=getchar())>=‘0‘&&ch‘9‘) Num=Num*10+ch-‘0‘;
10 return Num;
11 }
12 int N,M;
13 int C[100010],L[100010];
14 int to[100010],ne[100010],fir[100010],cnt=0;
15 void Add(int a,int b){
16 to[++cnt]=b;
17 ne[cnt]=fir[a];
18 fir[a]=cnt;
19 }
20 int lch[100010],rch[100010];
21 ll sum[100010];
22 int siz[100010],dis[100010];
23 ll ans=0;
24 int merge(int x,int y){
25 if(!x||!y) return x?x:y;
26 if(C[x]C[y]) swap(x,y);
27 rch[x]=merge(rch[x],y);
28 if(dis[lch[x]]dis[rch[x]]) swap(lch[x],rch[x]);
29 dis[x]=dis[rch[x]]+1;
30 sum[x]=sum[lch[x]]+sum[rch[x]]+C[x];
31 siz[x]=siz[lch[x]]+siz[rch[x]]+1;
32 return x;
33 }
34 int Build(int x){
35 int rt=x;
36 sum[rt]=C[x];
37 siz[rt]=1;
38 for(int i=fir[x];i!=-1;i=ne[i])
39 rt=merge(rt,Build(to[i]));
40 while(sum[rt]>M)
41 rt=merge(lch[rt],rch[rt]);
42 ans=max(ans,(ll)siz[rt]*L[x]);
43 return rt;
44 }
45 int main(){
46 memset(fir,-1,sizeof(fir));
47 N=readint();
48 M=readint();
49 for(int i=1;i){
50 int fa=readint();
51 C[i]=readint();
52 L[i]=readint();
53 Add(fa,i);
54 }
55 Build(1);
56 printf("%lld\n",ans);
57 return 0;
58 }
[BZOJ2809][Apio2012]dispatching 贪心+可并堆
标签：ems problem ring har font cst mem getc family
原文地址：http://www.cnblogs.com/halfrot/p/7625834.html
评论