17.10.16

• 上午
• 入门 配对堆（Pairing Heap）

强烈推荐 大米饼（兔）的Blog

贴上一个模板

const int MAXN=100005;
struct edge{
	int to,next; 
};
struct Recycle{
	int Res,Siz;
	int Stack[MAXN];
	Recycle(){Res=0;Siz=1;}
	int Get(){return Res?Stack[Res--]:Siz++;}
	void Save(int w){Stack[++Res]=w;}
};
struct PairingHeap{
	edge E[MAXN]; 
	Recycle ReNode,ReEdge;
	int Fa[MAXN],Head[MAXN],Val[MAXN],Q[MAXN<<1];
	int Root,Siz,L,R,L1,L2,kk;
	void Add(int u,int v){
		E[kk=ReEdge.Get()]=(edge){v,Head[u]}; Head[u]=kk;
		Fa[v]=u;
	}
	int Merge(int u,int v){
		if(Val[u]>Val[v]) swap(u,v);
		Add(u,v);
		return u;
	}
	void Push(int w){
		Val[kk=ReNode.Get()]=w;
		Head[kk]=Fa[kk]=0;
		Root=Root?Merge(Root,kk):kk;
	}
	int Top(){
		return Val[Root];
	}
	void Pop(){
		R=0;L=1;
		for(int i=Head[Root];i;i=E[i].next)
			Q[++R]=E[i].to,Fa[E[i].to]=0,ReEdge.Save(i);
		ReNode.Save(Root); Root=0;
		while(L<=R){
			if(L==R) {Root=Q[R]; return;}
			L1=Q[L++],L2=Q[L++];
			Q[++R]=Merge(L1,L2);
		}
	}
};

• 下午
• Ztraveler选讲
• 晚上
• BZOJ 2809 [Apio2012]dispatching

dfs时，对每个节点维护一个大根堆
维护该堆的节点数以及权值和
如果该大根堆的权值和大于m，则pop掉最大的元素 直到权值和小于m
然后回溯时，把儿子的堆与父亲的堆合并，
在每个节点处尝试更新一次答案。

配对堆实现。（常数比较大）

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
#define MAXN 100005
using namespace std;
struct edge{
	int to,next; 
}e[MAXN];
struct Recycle{
	int Res,Siz;
	int Stack[MAXN];
	Recycle(){Res=0;Siz=1;}
	int Get(){return Res?Stack[Res--]:Siz++;}
	void Save(int w){Stack[++Res]=w;}
};
struct PairingHeap{
	edge E[MAXN]; 
	Recycle ReNode,ReEdge;
	int Fa[MAXN],Head[MAXN],Root[MAXN],Q[MAXN<<1];
	ll Val[MAXN],Sum[MAXN],Num[MAXN];
	int L,R,L1,L2,kk;
	void Add(int u,int v){
		E[kk=ReEdge.Get()]=(edge){v,Head[u]}; Head[u]=kk;
		Fa[v]=u;
	}
	int Merge(int u,int v){
		if(Val[u]<Val[v]) swap(u,v); Add(u,v); 
		Sum[u]+=Sum[v]; Num[u]+=Num[v]; 
		return u;
	}
	void Push(int u,int w){
		Val[kk=ReNode.Get()]=w;
		Head[kk]=Fa[kk]=0;Sum[kk]=w;Num[kk]=1;
		Root[u]=Root[u]?Merge(Root[u],kk):kk;
	}
	ll Top(int u){
		return Val[Root[u]];
	}
	ll HSum(int u){
		return Sum[Root[u]];
	}
	ll HNum(int u){
		return Num[Root[u]];
	}
	void Pop(int u){
		R=0;L=1;
		for(int i=Head[Root[u]];i;i=E[i].next)
			Q[++R]=E[i].to,ReEdge.Save(i);
		ReNode.Save(Root[u]);Root[u]=0;
		while(L<=R){
			if(L==R) {Root[u]=Q[R];break;}
			L1=Q[L++],L2=Q[L++];
			Q[++R]=Merge(L1,L2);
		}
	}
};
PairingHeap H;
int head[MAXN];
ll sal[MAXN],abi[MAXN],m,ans;
int n,rt,ent=1;
void add(int u,int v){
	e[ent]=(edge){v,head[u]};
	head[u]=ent++;
}
void dfs(int u){
	H.Push(u,sal[u]);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		dfs(v);
		H.Root[u]=H.Merge(H.Root[u],H.Root[v]);
	}
	while(H.HSum(u)>m) H.Pop(u);
	ans=max(ans,H.HNum(u)*abi[u]);
}
int main(){
	scanf("%d%lld",&n,&m);
	for(int i=1,f;i<=n;i++){
		scanf("%d%lld%lld",&f,&sal[i],&abi[i]);
		if(!f) rt=i;
		else add(f,i);
	}
	dfs(rt);
	printf("%lld",ans);
	return 0;
}

17.10.16

原文：http://www.cnblogs.com/zj75211/p/7679106.html