APIO2012 派遣
标签：color temp 描述 apio2012 print space problem lan sum
题目描述
题解：
可并堆优化$dp$。
由于$ans$只由$l$与派遣人数决定，我们可以贪心选取总和$
有两种选择，一种是维护小根堆，一直$pop$到弹出的总和$>m$；
另一种是维护大根堆，一直$pop$到剩下总和$
这两种比较一定是维护大根堆更优，因为每次$pop$后剩下的堆可以直接回溯。
然后$dp$就好了。
代码：
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 100050;
template
inline void read(T&x)
{
T f = 1,c = 0;char ch=getchar();
while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch‘9‘){c=c*10+ch-‘0‘;ch=getchar();}
x = f*c;
}
int n,b[N],c[N],hed[N],cnt,rt[N],dis[N],ls[N],rs[N],siz[N];
ll m,l[N],ans=0,sum[N];
struct EG
{
int to,nxt;
}e[N];
void ae(int f,int t)
{
e[++cnt].to = t;
e[cnt].nxt = hed[f];
hed[f] = cnt;
}
int merge(int x,int y)
{
if(!x||!y)return x+y;
if(c[x]c[y])swap(x,y);
rs[x] = merge(rs[x],y);
if(dis[ls[x]]dis[rs[x]])swap(ls[x],rs[x]);
dis[x] = dis[rs[x]]+1;
return x;
}
int pop(int x)
{
return merge(ls[x],rs[x]);
}
struct Pair
{
int x;
ll w;
Pair(){}
Pair(int x,ll w):x(x),w(w){}
friend bool operator (Pair a,Pair b)
{
return a.w b.w;
}
};
int cal(int u)
{
while(sum[u]>m)
{
sum[u]-=c[rt[u]];
rt[u]=pop(rt[u]);
siz[u]--;
}
return siz[u];
}
void dfs(int u)
{
siz[u]=1;sum[u]=c[u];
for(int j=hed[u];j;j=e[j].nxt)
{
int to = e[j].to;
dfs(to);
siz[u]+=siz[to];
sum[u]+=sum[to];
rt[u] = merge(rt[u],rt[to]);
}
ans = max(ans,l[u]*cal(u));
}
int main()
{
read(n),read(m);
for(int i=1;i)
{
read(b[i]),read(c[i]),read(l[i]);
ae(b[i],i);
rt[i]=i,dis[i]=1;
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
APIO2012 派遣
标签：color temp 描述 apio2012 print space problem lan sum
原文地址：https://www.cnblogs.com/LiGuanlin1124/p/10294989.html
评论