关于斐波那契堆
  • 板块学术版
  • 楼主critnos
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/9/18 13:40
  • 上次更新2023/11/5 13:03:28
查看原帖
关于斐波那契堆
203623
critnos楼主2020/9/18 13:40

写完了觉得常数非常大。。而且只实现了优先队列的三个操作。。请问能怎么卡常。。

struct fib_heap
{
	#define it list<int>::iterator
	struct node
	{
		vector<int> son;
		int v;
		int de;
	}t[1000005];
	int minn,size_,wz,color;
	it to_min;
	list<int> rt_list,ans_list;
	it del[1000005];
	int col[1000005];
	it ix[1000005];
	fib_heap()
	{
		minn=INT_MAX;
		wz=size_=0;
		color=0;
	}
	int new_node(int x)
	{
		t[++wz]=node({vector<int>(),x,0});
		return wz;
	}
	void push(int x)
	{
		rt_list.push_back(new_node(x));
		if(minn>x)
		{
			minn=x;
			to_min=--rt_list.end();
		}
		size_++;
	}
	bool empty()
	{
		return !size_;
	}
	int size()
	{
		return size_;
	}
	int top()
	{
		return minn;
	}
	it merge(it x,it y)
	{
		if(t[*x].v>t[*y].v) swap(*x,*y);
		int wx=*x,wy=*y;
		t[*x].son.push_back(*y);
		ans_list.erase(y);
		t[*x].de++;
		return x;
	}
	int pop()
	{
		if(size_==0) return INT_MAX;
		color++;
		size_--;
		int ret=minn,i,dell,w;
		dell=*to_min;
		for(i=0;i<t[dell].son.size();i++)
			rt_list.push_back(t[dell].son[i]);
		rt_list.erase(to_min);
		int cnt=0;
		for(it i=rt_list.begin();i!=rt_list.end();i++,cnt++)
		{
			ans_list.push_back(*i);
			it q=--ans_list.end();
			while(col[t[*q].de]==color)
			{
				col[t[*q].de]=0;
				q=merge(q,ix[t[*q].de]);
			}	
			ix[t[*q].de]=q;
			col[t[*q].de]=color;
		}
		rt_list=ans_list;
		ans_list.clear();
		minn=INT_MAX;
		for(it i=rt_list.begin();i!=rt_list.end();i++)
			if(t[*i].v<minn)
				minn=t[*i].v,to_min=i;
		return ret;
	}
};
2020/9/18 13:40
加载中...