APIO2012 派遣dispatching | 左偏树

题目链接:戳我

就是尽可能地选取排名小的,加起来就可以了。然后我们考虑利用一个大根堆,一个一个合并,如果超过派遣的钱,我们就把费用最大的那个忍者丢出队列。

左偏树,作为一个十分优秀的可并堆,我们这道题利用的就是这个数据结构。

左偏树不会?戳我

这里有一张来自HolseLee dalao的图:

APIO2012 派遣dispatching | 左偏树

因为是从下往上合并嘛。。所以dfs整棵树的时候一定注意要先把dfs递归放下去,等把所有的子树都处理完之后,才可以开始处理自己呀!!

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,m,root,tt;
int v[MAXN],rt[MAXN],siz[MAXN],head[MAXN];
long long ans,sum[MAXN];
struct Node{int ls,rs,dis,fa;long long val;}t[MAXN];
struct Edge{int nxt,to;}edge[MAXN<<1];
inline void add(int from,int to){edge[++tt].nxt=head[from],edge[tt].to=to,head[from]=tt;}
inline int merge(int x,int y)
{
if(t[x].val==-1) x=0;
if(t[y].val==-1) y=0;
if(x==0||y==0) return x+y;
if(t[x].val<t[y].val) swap(x,y);
t[x].rs=merge(t[x].rs,y);
t[t[x].rs].fa=x;
if(t[t[x].ls].dis<t[t[x].rs].dis) swap(t[x].ls,t[x].rs);
t[x].dis=t[t[x].rs].dis+1;
return x;
}
inline int pop(int x)
{
t[t[x].ls].fa=t[t[x].rs].fa=0;
t[x].val=-1;
return merge(t[x].ls,t[x].rs);
}
inline void dfs(int x)
{
sum[x]=t[x].val,siz[x]=1;
for(int i=head[x];i;i=edge[i].nxt)
{
dfs(edge[i].to);
sum[x]+=sum[edge[i].to];
siz[x]+=siz[edge[i].to];
}
for(int i=head[x];i;i=edge[i].nxt)
rt[x]=merge(rt[x],rt[edge[i].to]);
while(sum[x]>m&&siz[x])
{
siz[x]--;
sum[x]-=t[rt[x]].val;
rt[x]=pop(rt[x]);
}
ans=max(ans,(long long)siz[x]*v[x]);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int ff;
scanf("%d%lld%d",&ff,&t[i].val,&v[i]);
add(ff,i);
if(ff==0) root=i;
rt[i]=i;
}
dfs(root);
printf("%lld\n",ans);
return 0;
}

本来想写一个pb_ds版本的,但是好像玩不转啊qwq呜呜呜 哪个大佬来教教我啊

上一篇:ecs使用感受


下一篇:决策树-更新