重新学了一发配对堆

一篇不错的讲解:

http://wenku.baidu.com/link?url=N5FTv6Grq7pDfM20LdB4nk7nxvu6ALEtuh5WYxDPqPJjVBbk_rSw65yO3OIeMP5Mq6MMR1FbKLDn5SVkK77scP9lsFLyZFd-l7WZS0I_uOq

很多时候根本不需要left(last)指针,只需要child指针和right即可..

比如这题..我们需要一个join,link和delete_node就够了..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int father[100005],c[100005],l[100005];
struct node
{
    int y;
    node * ch;
    node * next;
};
node * root[100005];
node * new_node()
{
    static node a[100005];
    static int top=0;
    return &a[top++];
}
int size[100005];
node * join(node * x,node * y)
{
    if (x->y>y->y) swap(x,y);
    x->next=y->ch;
    y->ch=x;
    return y;
}
node * link(node * x)
{
    node * y=x->next;
    x->next=0;
    if (y==0) return x;
    node * z=y->next;
    if (z==0) return join(x,y);
    y->next=0;
    return join(link(z),join(x,y));
}
void delete_node(node * &x)
{
    x=link(x->ch);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d%d%d",&father[i],&c[i],&l[i]);
        father[i]--;
    }
    for (i=0;i<n;i++)
    {
        root[i]=new_node();
        root[i]->ch=0;
        root[i]->next=0;
        root[i]->y=c[i];
        size[i]=1;
    }
    long long ans=0;
    for (i=n-1;i>=0;i--)
    {
        ans=max(ans,(long long)size[i]*l[i]);
        if (i!=0)
        {
            root[father[i]]=join(root[i],root[father[i]]);
            c[father[i]]+=c[i];
            size[father[i]]+=size[i];
            for (;c[father[i]]>m;)
            {
                size[father[i]]--;
                c[father[i]]-=root[father[i]]->y;
                delete_node(root[father[i]]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}