[TIOJ] 1429. [APIO '12] 忍者調度問題
題目連結:http://tioj.infor.org/problems/1429
本題其實有很多種寫法,例如:樹剖、整體二分搜、堆(啟發式合併或可合併),我這裡的做法是用可合併堆的做法,也是裡面最快的一種(?,可以發現對於某個節點,如果已知他所有小孩的選法,那就把那些節點全部混在一起,然後如果超過預算就把最大的移掉,而因為要找最大的,我們需要用到heap,不過我們還需要快速合併多個堆,所以可以採用可合併堆,或是直接啟發式合併就好。
我在這裡採用的可合併堆是配對堆,雖然大家都寫左偏樹,不過我覺得配對堆比較好寫XDD,一種似乎均攤複雜度接近費波那契堆的東東,詳細證明可以看他的論文,不過我也不是很熟,簡單說一下他的做法:合併跟插入都是直接跟根比大小後決定誰當根,所以有可能一個根下面有一堆小孩,為了解決會因此爛掉的狀況,於使我們在pop的時候讓他的小孩們緊縮一點(?,就是pop時就把他的小孩兩兩合併,直到剩一個為止。似乎跟splay tree有點類似,大概這樣吧
註:這裡採用的合併方式因為有點懶人,根據論文他只能證出$O(\frac{log n log log n}{ log log log n})$的上界,不過$ \frac{ \frac{log n log log n}{ log log log n} }{log n}$在$n < 10^9$時只大約等於2而已
本題其實有很多種寫法,例如:樹剖、整體二分搜、堆(啟發式合併或可合併),我這裡的做法是用可合併堆的做法,也是裡面最快的一種(?,可以發現對於某個節點,如果已知他所有小孩的選法,那就把那些節點全部混在一起,然後如果超過預算就把最大的移掉,而因為要找最大的,我們需要用到heap,不過我們還需要快速合併多個堆,所以可以採用可合併堆,或是直接啟發式合併就好。
我在這裡採用的可合併堆是配對堆,雖然大家都寫左偏樹,不過我覺得配對堆比較好寫XDD,一種似乎均攤複雜度接近費波那契堆的東東,詳細證明可以看他的論文,不過我也不是很熟,簡單說一下他的做法:合併跟插入都是直接跟根比大小後決定誰當根,所以有可能一個根下面有一堆小孩,為了解決會因此爛掉的狀況,於使我們在pop的時候讓他的小孩們緊縮一點(?,就是pop時就把他的小孩兩兩合併,直到剩一個為止。似乎跟splay tree有點類似,大概這樣吧
註:這裡採用的合併方式因為有點懶人,根據論文他只能證出$O(\frac{log n log log n}{ log log log n})$的上界,不過$ \frac{ \frac{log n log log n}{ log log log n} }{log n}$在$n < 10^9$時只大約等於2而已
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
#define N 100000
struct pairingNode{
int val;
vector<pairingNode*> child;
};
class pairingHeap{
private:
pairingNode* root;
int count;
public:
lld sum=0;
pairingHeap(){root=NULL;count=0;}
inline bool empty(){return count==0;}
inline int top(){return root->val;}
inline int size(){return count;}
inline void push(lld a){
sum+=a;
count++;
if(root==NULL){
root = new pairingNode;
root->val=a;
}else{
auto temp = new pairingNode;
temp->val=a;
if(root->val>=temp->val)
root->child.PB(temp);
else{
temp->child.PB(root);
swap(temp,root);
}
}
}
inline void join(pairingHeap& a){
sum+=a.sum;
count+=a.size();
auto temp = a.root;
if(root->val>=temp->val){
root->child.PB(temp);
}else{
temp->child.PB(root);
swap(temp,root);
}
}
inline void pop(){
sum-=root->val;
count--;
queue<pairingNode*> QQ;
for(auto i:root->child) QQ.push(i);
delete root;
while(QQ.size()>1){
pairingNode* tp1=QQ.front();QQ.pop();
pairingNode* tp2=QQ.front();QQ.pop();
if(tp1->val>tp2->val){
tp1->child.PB(tp2);
QQ.push(tp1);
}else{
tp2->child.PB(tp1);
QQ.push(tp2);
}
}
if(QQ.empty()) root=NULL;
else root = QQ.front();
}
};
struct ninja{
lld leader,cost;
vector<int> child;
};
ninja people[N+5];
lld ans=0,maxCost;
void DFS(int,pairingHeap&);
int main(int argc, char* argv[]){
int n,root;
scanf("%d%lld",&n,&maxCost);
for(int i=0;i<n;i++){
int ll;
scanf("%d%lld%lld",&ll,&people[i].cost,&people[i].leader);
if(ll!=0) people[ll-1].child.PB(i);
else root=i;
}
pairingHeap each;
DFS(root,each);
printf("%lld",ans);
return 0;
}
void DFS(int w, pairingHeap& cur){
cur.push(people[w].cost);
for(auto i:people[w].child){
pairingHeap each;
DFS(i,each);
cur.join(each);
}
while(cur.sum>maxCost) cur.pop();
ans = max(ans, people[w].leader*cur.size());
}
你實作的不是標準的 pairing heap 喔
回覆刪除根據原論文 13 頁之後的內容
你實作的是 multipass variant
複雜度不是 O(log n)
而是 O(log n log log n / log log log n) 喔
感謝指正,已修正
刪除不過其實
(log n log log n / log log log n)/(log n)
在10^9以內都接近2