BZOJ2809: [Apio2012]dispatching

2021-04-21 17:28

阅读：568

给n

其实就是要合并。平衡树、线段树、可并堆挑一个。

可并堆由于没法二分，故“正难取反”，维护最大的，在不够装时弹掉。

 1 #includestring.h>
 2 #include 3 #include 4 #include 5 //#include
 6 #include
 7 //#include
 8 using namespace std;
 9 
10 int n,m;
11 #define maxn 100011
12 struct Edge{int to,next;}edge[maxn1]; int first[maxn],le=2;
13 void in(int x,int y) {Edge &e=edge[le]; e.to=y; e.next=first[x]; first[x]=le++;}
14 void insert(int x,int y) {in(x,y); in(y,x);}
15 
16 #define LL long long
17 struct leftist
18 {
19     struct Node
20     {
21         int size,ls,rs,dis,v; LL sum;
22     }a[maxn];
23     leftist() {a[0].dis=-1;}
24     int merge(int x,int y)
25     {
26         if (!x || !y) return x^y;
27         if (a[x].vint t=x; x=y; y=t;}
28         a[x].rs=merge(a[x].rs,y);
29         if (a[a[x].ls].disint t=a[x].ls; a[x].ls=a[x].rs; a[x].rs=t;}
30         a[x].dis=a[a[x].rs].dis+1;
31         a[x].size=a[a[x].ls].size+a[a[x].rs].size+1;
32         a[x].sum=a[a[x].ls].sum+a[a[x].rs].sum+a[x].v;
33         return x;
34     }
35     void push(int id,int &root,int val)
36     {
37         a[id].v=val; a[id].size=1; a[id].sum=val;
38         a[id].ls=a[id].rs=a[id].dis=0;
39         root=merge(root,id);
40     }
41     void pop(int &root) {root=merge(a[root].ls,a[root].rs);}
42     int top(int root) {return a[root].v;}
43 }q;
44 int root[maxn];
45 int find(int x) {return x==root[x]?x:(root[x]=find(root[x]));}
46 
47 int b[maxn]; LL ans=-1e18;
48 void dfs(int x)
49 {
50     for (int i=first[x];i;i=edge[i].next)
51     {
52         const Edge &e=edge[i];
53         dfs(e.to);
54         root[x]=q.merge(root[x],root[e.to]);
55     }
56     while (q.a[root[x]].sum>m) q.pop(root[x]);
57     ans=max(ans,q.a[root[x]].size*1ll*b[x]);
58 }
59 
60 int main()
61 {
62     scanf("%d%d",&n,&m);
63     int rr=0;
64     for (int i=1,x,y;i)
65     {
66         scanf("%d%d%d",&x,&y,&b[i]);
67         if (x==0) rr=i; else in(x,i);
68         q.push(i,root[i],y);
69     }
70     dfs(rr);
71     printf("%lld\n",ans);
72     return 0;
73 }

View Code

上一篇：c# 使用正则解析html

下一篇：C#图解：第七章

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ2809: [Apio2012]dispatching
文章链接：http://soscw.com/index.php/essay/77702.html

亲，登录后才可以留言！

BZOJ2809: [Apio2012]dispatching

评论

热门文章

推荐文章

最新文章

置顶文章