Description
在一個(gè)忍者的幫派里，一些忍者們被選中派遣給顧客，然后依據(jù)自己的工作獲取報(bào)償。在這個(gè)幫派里，有一名忍者被稱之為 Master。除了 Master以外，每名忍者都有且僅有一個(gè)上級(jí)。為保密，同時(shí)增強(qiáng)忍者們的領(lǐng)導(dǎo)力，所有與他們工作相關(guān)的指令總是由上級(jí)發(fā)送給他的直接下屬，而不允許通過(guò)其他的方式發(fā)送。現(xiàn)在你要招募一批忍者，并把它們派遣給顧客。你需要為每個(gè)被派遣的忍者 支付一定的薪水，同時(shí)使得支付的薪水總額不超過(guò)你的預(yù)算。另外，為了發(fā)送指令，你需要選擇一名忍者作為管理者，要求這個(gè)管理者可以向所有被派遣的忍者 發(fā)送指令，在發(fā)送指令時(shí)，任何忍者（不管是否被派遣）都可以作為消息的傳遞 人。管理者自己可以被派遣，也可以不被派遣。當(dāng)然，如果管理者沒有被排遣，就不需要支付管理者的薪水。你的目標(biāo)是在預(yù)算內(nèi)使顧客的滿意度最大。這里定義顧客的滿意度為派遣的忍者總數(shù)乘以管理者的領(lǐng)導(dǎo)力水平，其中每個(gè)忍者的領(lǐng)導(dǎo)力水平也是一定的。寫一個(gè)程序，給定每一個(gè)忍者 i的上級(jí) Bi，薪水Ci，領(lǐng)導(dǎo)力L i，以及支付給忍者們的薪水總預(yù)算 M，輸出在預(yù)算內(nèi)滿足上述要求時(shí)顧客滿意度的最大值。

1 ≤N ≤ 100,000 忍者的個(gè)數(shù)；
1 ≤M ≤ 1,000,000,000 薪水總預(yù)算；
0 ≤Bi < i 忍者的上級(jí)的編號(hào)；
1 ≤Ci ≤ M 忍者的薪水；
1 ≤Li ≤ 1,000,000,000 忍者的領(lǐng)導(dǎo)力水平。

Input
從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。
第一行包含兩個(gè)整數(shù) N和 M，其中 N表示忍者的個(gè)數(shù)，M表示薪水的總預(yù)算。
接下來(lái) N行描述忍者們的上級(jí)、薪水以及領(lǐng)導(dǎo)力。其中的第 i 行包含三個(gè)整 Bi , C i , L i分別表示第i個(gè)忍者的上級(jí)，薪水以及領(lǐng)導(dǎo)力。Master滿足B i = 0，并且每一個(gè)忍者的老板的編號(hào)一定小于自己的編號(hào) Bi < i。
Output
輸出一個(gè)數(shù)，表示在預(yù)算內(nèi)顧客的滿意度的最大值。

Sample Input
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
Sample Output
6

HINT
如果我們選擇編號(hào)為 1的忍者作為管理者并且派遣第三個(gè)和第四個(gè)忍者，薪水總和為 4，沒有超過(guò)總預(yù)算 4。因?yàn)榕汕擦?2 個(gè)忍者并且管理者的領(lǐng)導(dǎo)力為3，用戶的滿意度為 2,是可以得到的用戶滿意度的最大值。

我們需要處理出每個(gè)節(jié)點(diǎn)的孩子中滿足條件的盡可能多的節(jié)點(diǎn)，但是我們?nèi)绻麖纳贤卤闅v處理的話顯然會(huì)超時(shí)O(n^2)。

所以我們需要從下往上進(jìn)行處理，盡可能地利用以前的信息，所以不妨對(duì)每個(gè)節(jié)點(diǎn)使用一個(gè)優(yōu)先隊(duì)列，將滿足條件的都放進(jìn)去，如果工資已經(jīng)高于能負(fù)擔(dān)的工資，就把工資最高的那個(gè)人去掉。然后將相鄰兩個(gè)節(jié)點(diǎn)進(jìn)行合并。為了提高效率，我們應(yīng)當(dāng)先處理重孩子，再處理輕孩子。

可是這樣使用STL自帶的優(yōu)先隊(duì)列復(fù)雜度還不夠優(yōu)秀，我們可以針對(duì)這個(gè)問題實(shí)現(xiàn)我們自己的優(yōu)先隊(duì)列，所用的數(shù)據(jù)結(jié)構(gòu)就是左偏樹

左偏樹是一種二叉堆，這種堆可以合并出高度比較低的樹，具體就是通過(guò)節(jié)點(diǎn)x到?jīng)]有右子樹的節(jié)點(diǎn)y的距離來(lái)進(jìn)行判斷，及時(shí)交換左右孩子，從而使得堆不會(huì)變得很長(zhǎng)。

這樣的堆有利于再和其他的堆進(jìn)行合并。

合并的時(shí)候：從上往下合并，不斷地把根節(jié)點(diǎn)更大的右兒子和另一個(gè)堆合并。（可以證明這樣的復(fù)雜度最優(yōu)秀）

具體到這個(gè)問題中，我們用節(jié)點(diǎn)類型存儲(chǔ)每個(gè)節(jié)點(diǎn)的數(shù)據(jù)，可是每個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)卻不一定是他本身，在二叉堆構(gòu)造過(guò)程中，原本的位置已經(jīng)改變，為了記錄這種改變，我們用root數(shù)組記錄在左偏樹中該節(jié)點(diǎn)的父親節(jié)點(diǎn)。（在訪問到他為止左偏樹中的節(jié)點(diǎn)都是實(shí)際樹形關(guān)系中他的孩子和他本身）

當(dāng)目前工資已經(jīng)超過(guò)最大工資的時(shí)候，我們就刪去堆頂元素（貪心思想，堆頂?shù)墓べY最高，刪去他最劃算）

借鑒了網(wǎng)上的代碼加上自己的思考，發(fā)現(xiàn)自己這樣寫雖然沒有什么錯(cuò)誤，但是還是應(yīng)該把用于記錄堆關(guān)系的和用于記錄樹關(guān)系的數(shù)據(jù)分開，混在一起導(dǎo)致容易理解錯(cuò)誤。

#include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> #include<set> #include<map> #include<cmath> #define rep(i,x,n) for(register int i=x;i<=n;i++) using namespace std;typedef long long ll; const int MAXN=1e5+5; struct Node {int cost; ll ctrl;int rson,lson,dis; }Tree[MAXN]; int nex[MAXN]; int head[MAXN],num=0; int N; ll M; int root[MAXN],sz[MAXN]; ll sum[MAXN]; ll ans=0;int Merge(int x,int y) {if(!x || !y) return x+y;if(Tree[x].cost<Tree[y].cost) swap(x,y);Tree[x].rson=Merge(Tree[x].rson,y);if(Tree[Tree[x].rson].dis> Tree[Tree[x].lson].dis) swap(Tree[x].rson,Tree[x].lson);Tree[x].dis=Tree[Tree[x].rson].dis+1;return x; }void Delete(int& x) {x=Merge(Tree[x].lson,Tree[x].rson); }int dfs(int x) {root[x]=x;sum[x]=Tree[x].cost; sz[x]=1;for(int i=head[x];i;i=nex[i]){dfs(i);root[x]=Merge(root[x],root[i]);sum[x]+=sum[i]; sz[x]+=sz[i];}while(sum[x]>M){sum[x]-=Tree[root[x]].cost;sz[x]--;Delete(root[x]);}ans=max(ans,sz[x]*Tree[x].ctrl); }int main() {scanf("%d%lld",&N,&M);int t; //int Master=-1;rep(i,1,N){scanf("%d",&t);//if(t==0) Master=i;nex[i]=head[t]; head[t]=i;scanf("%d%lld",&Tree[i].cost,&Tree[i].ctrl);}dfs(1);printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ2809-左偏树合并的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。