[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而已
#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());
}

留言

  1. 你實作的不是標準的 pairing heap 喔
    根據原論文 13 頁之後的內容
    你實作的是 multipass variant
    複雜度不是 O(log n)
    而是 O(log n log log n / log log log n) 喔

    回覆刪除
    回覆
    1. 感謝指正,已修正
      不過其實
      (log n log log n / log log log n)/(log n)
      在10^9以內都接近2

      刪除

張貼留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

[IOJ] 19. 啦啦啦

[IOJ] 14. 費氏數列問題