BZOJ2809 [Apio2012]dispatching 可并堆
2021-04-22 05:27
阅读：523
欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ2809
题意概括
n个点组成一棵树，每个点都有一个领导力和费用，可以让一个点当领导，然后在这个点的子树中选择一些费用之和不超过m的点，得到领导的领导力乘选择的点的个数（领导可不被选择）的利润。求利润最大值。n≤100000
题解
做一个类似树形dp的操作。
维护大根堆，每次从子节点到父节点就是合并所有的子节点的堆。
利用左偏树。
然后先删掉大的，直到合法为止。
好像没什么要讲的。
代码
#include#include #include #include #include using namespace std; typedef long long LL; const int N=100005; struct Gragh{ int cnt,y[N],nxt[N],fst[N]; void clear(){ cnt=0; memset(fst,0,sizeof fst); } void add(int a,int b){ y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt; } }g; int n,m,L[N],fa[N],C[N],root[N],cnt[N]; struct heap{ int ls,rs,v,len; void set(int a,int b,int c,int d){ ls=a,rs=b,v=c,len=d; } }h[N]; LL ans=0,tot[N]; LL max(LL a,LL b){ return a>b?a:b; } int merge(int a,int b){ if (a==0||b==0) return a+b; if (h[a].v m){ tot[rt]-=h[root[rt]].v; root[rt]=merge(h[root[rt]].ls,h[root[rt]].rs); cnt[rt]--; } ans=max(ans,1LL*L[rt]*cnt[rt]); } int main(){ scanf("%d%d",&n,&m); g.clear(); for (int i=1;i
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ2809 [Apio2012]dispatching 可并堆
文章链接：http://soscw.com/index.php/essay/77937.html
文章标题：BZOJ2809 [Apio2012]dispatching 可并堆
文章链接：http://soscw.com/index.php/essay/77937.html
评论
亲，登录后才可以留言！