p1552 [APIO2012]派遣

2021-06-16 05:05

阅读：444

标签：while 分析 main out scanf name i++ sig 启发式合并

传送门

分析

首先这个题有两个坑点

一是一个点不管可以由父亲领导，任何祖宗均可领导

而是根节点的花费要算在总费用中且它自己也算在总节点数量中

于是我们考虑如何求答案

首先我们知道对于一个点如果在一个子树中就没有选则在更大的一棵子树中一定不会选

因为一棵大的子树有更多选择，结果肯定不会比它的子树劣

于是我们可以每个节点开一个优先队列，每次将超过范围的点直接删掉

于是合并两棵子树是暴力启发式合并即可

代码

#include
#include
#include
#includestring>
#include
#include
#include
#include
#include
#include
#include
#includeset>
#include
#includeusing namespace std;
#define int long long
vectorint>v[100100];
int c[100100],l[100100],now[100100],d[100100],sum[100100],n,m,Ans;
priority_queueint>q[100100];
inline void mer(int u,int x,int y){
    if(q[x].size()q[y].size()){
      swap(x,y);
      now[u]=x;
    }
    while(!q[y].empty()){
      q[x].push(q[y].top());
      q[y].pop();
    }
}
inline void del(int x){
    while(sum[x]>m){
      sum[x]-=q[now[x]].top();
      q[now[x]].pop();
    }
}
inline void work(int x){
    now[x]=x;
    q[now[x]].push(c[x]);
    sum[x]+=c[x];
    for(int i=0;i){
      work(v[x][i]);
      sum[x]+=sum[v[x][i]];
      mer(x,now[x],now[v[x][i]]);
    }
    del(x);
    int y=q[now[x]].size();
    if(y*l[x]>Ans)Ans=y*l[x];
}
signed main(){
    int i,j,k;
    scanf("%lld%lld",&n,&m);
    for(i=1;i){
      scanf("%lld%lld%lld",&k,&c[i],&l[i]);
      if(k){
        v[k].push_back(i);
        d[i]++;
      }
    }
    for(i=1;i)
      if(!d[i])work(i);
    coutAns;
    return 0;
}

p1552 [APIO2012]派遣

标签：while 分析 main out scanf name i++ sig 启发式合并

原文地址：https://www.cnblogs.com/yzxverygood/p/10353088.html

上一篇：windows平台下安装linux

下一篇：关于Delphi内存表的使用说明

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：p1552 [APIO2012]派遣
文章链接：http://soscw.com/essay/94451.html

亲，登录后才可以留言！

p1552 [APIO2012]派遣

评论

热门文章

推荐文章

最新文章

置顶文章