@ysner
2018-04-21T11:09:49.000000Z
字数 1650
阅读 2186
贪心
原题
某省选强化题
大致意思是给你一颗树,选父亲后才能选儿子。
每个点对答案的贡献为你在第几次选这个点 × 该点权值
问取完所有点最小答案是多少。
贪心没学好,_ _ _ _ _(自己yy)
答案要求的其实是个选取序列。。。
我们可以发现,要保证答案最优性,最大点取的时间越小越好。
又可以发现,只要最大点父亲已选,下一个点选最大点肯定最优。
这时我们确定了一部分顺序,可以想,为什么不能把已确定的、前后相邻选的两点合并起来呢?
现在问题就是如何在几个大点中作抉择了。
可以发现,此时如果大点越大(是权值和,是时间和),就是性价比越高,先选越优。
显然看起来有点鬼
我们要用更有区分度的比较方式
如果
那么
于是每次按着贪心策略合并点,对答案的贡献为其父亲选完所用时间×点权值,再把新点与被合并点的儿子相连即可。
int main()
{
while(233)
{
memset(h,-1,sizeof(h));ans=0;cnt=0;
n=gi();r=gi();
if(!n&&!r) break;t[0]=1;
fp(i,1,n) a[i]=gi(),t[i]=1;
fp(i,1,n-1)
{
re int u=gi(),v=gi();
add(u,v);f[v]=u;
}
f[r]=0;
re int res=n;
while(res--)
{
re int mx=1;
fp(i,2,n)
if(a[i]*t[mx]>a[mx]*t[i]) mx=i;
ans+=a[mx]*t[f[mx]];
a[f[mx]]+=a[mx];t[f[mx]]+=t[mx];
for(re int i=h[mx];i+1;i=e[i].nxt)
{
re int v=e[i].to;
f[v]=f[mx];
add(f[mx],v);
}
a[mx]=-1;
}
printf("%lld\n",ans);
}
return 0;
}
Update:发现一个很蛋疼的问题:用并查集就不用新建边了。
裸贪心是的。
我们需要一个能马上提供最大点的堆来降低复杂度。
struct node{int u,sz;ll w;bool operator < (const node &o) const {return w*o.sz>o.w*sz;}};
priority_queue<node> Q;
il void dfs(re int u)
{
vis[u]=1;++tim;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(vis[v]) {puts("-1");exit(0);}
dfs(v);
}
}
il int find(re int x){return x==F[x]?x:F[x]=find(F[x]);}
int main()
{
memset(h,-1,sizeof(h));ans=0;
n=gi();
fp(i,1,n) f[i]=gi(),add(f[i],i);
dfs(0);if(tim<=n) return puts("-1"),0;
fp(i,0,n) F[i]=i,sz[i]=1;
fp(i,1,n) w[i]=gi(),Q.push((node){i,1,w[i]});
re int u,p;
while(!Q.empty())
{
node s=Q.top();Q.pop();u=find(s.u);
if(sz[u]^s.sz) continue;//扔掉不符合当前情况的决策
F[u]=p=find(f[u]);
ans+=w[u]*sz[p];
w[p]+=w[u];sz[p]+=sz[u];
if(p) Q.push((node){p,sz[p],w[p]});
}
printf("%lld\n",ans);
return 0;
}