写完了觉得常数非常大。。而且只实现了优先队列的三个操作。。请问能怎么卡常。。
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;
}
};