题意:对于a数组,求它的一个合法排列的最大权值。合法排列:对于任意j,k,如果a[p[j]]=p[k],那么k<j。

权值:sigma(a[p[i]]*i)。n<=50W。

标程:

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
ll x=,f=;char ch=getchar();
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();
return x*f;
}
const int N=;
vector<ll> vec[N];
ll ans,sum[N],he[N],cnt,head[N],n,a[N],fa[N],w[N],sz[N],cn,vis[N],tail[N],f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
struct _node{ll sum,he,sz,id;_node(ll A,ll B,ll C,ll D){sum=A;he=B;sz=C;id=D;}};
struct cmp{
bool operator () (const _node &A,const _node &B)
{return A.he*B.sz>B.he*A.sz||A.he*B.sz==B.he*A.sz&&A.sz<B.sz;}
};
priority_queue<_node,vector<_node>,cmp> q;
int main()
{
n=read();
for (int i=;i<=n;i++) f[i]=i;
for (int i=;i<=n;i++)
{
a[i]=read();
if (<a[i]&&a[i]<=n) vec[a[i]].push_back(i),fa[i]=a[i]; else fa[i]=-;
}
for (int i=;i<=n;i++) w[i]=read(),q.push(_node(sum[i]=w[i],he[i]=w[i],sz[i]=,i));
while (!q.empty())
{
int x=q.top().id,fx=fa[find(x)];q.pop();
if (vis[x]) continue; vis[x]=; //dijkstra的思想,肯定先访问最后一次合并过的点,其他过去版本直接continue,这样就不用再记录一个del的堆。
if (fx==-)
{
ans+=sum[x]+cn*he[x];
for (int i=;i<vec[x].size();i++) fa[vec[x][i]]=-;
cn+=sz[x];
}
else {
if (vis[fx]) return puts("-1"),;
for (int i=;i<vec[x].size();i++) f[vec[x][i]]=find(x);
sum[fx]+=sum[x]+he[x]*sz[fx];he[fx]+=he[x];sz[fx]+=sz[x];
q.push(_node(sum[fx],he[fx],sz[fx],fx));
}
}
printf("%lld\n",ans);
return ;
}

易错点:1.居然碰到了yhx钦定的最难调错误没有之一,记!

return A.he*B.sz>B.he*A.sz||A.he*B.sz==B.he*A.sz&&A.sz<B.sz;
如果不判定相等的情况就不一定取到最后一个。

2.判断无解:vis表示已经被合并/删除的节点,重新连爸爸后爸爸应该是没有被删除的,如果vis[fa]=1,那么必然矛盾。

3.更改父亲的操作如果用vector暴力加,时间复杂度会到O(n^2)。用并查集保存同父亲的点是最快的做法。

题解:堆+并查集+建树+贪心

做法好神。如果a[p[j]]=p[k],那么k<j:也就是说比如a[1]=3,那么在排列中3一定在1前面。对于1<=a[i]<=n的点,连边a[i]->i,表示先取a[i],再取i。那么就形成了一棵树,如果有环必然无解。

这棵树肯定是每次取一个没有父亲的点作为p[i]。基于贪心,i越小,选越小的w[i]更优。

因此我们每次用堆/set维护权值最小的点,如果它没有父亲肯定直接取走,反之和其父亲合并,表示如果取走父亲后接下来肯定就取它。

合并之后,该点的儿子都连边向它父亲,也就是说fa[son[x]]=fa[x],可以用并查集维护。这样这个点的权值用sigma/size来代替。

可以证明:1.比较两个点的sigma/size就相当于比较它们sigma(i*w[p[i]])的权值。

2.对于同一个点,sigma/size随着合并不严格单调减。(设he1/sz1<he2/sz2,那么1向2合并,必然有he2/sz2>(he1+he2)/(sz1+sz2)。化简he2/sz2>(he1+he2)/(sz1+sz2),则he1*sz2<he2*sz1,同假设成立)

时间复杂度O(nlogn+na(n))。

最新文章

  1. mako模板调试与使用技巧
  2. android如何获取到启动类的包和类路径
  3. spring mvc 请求转发和重定向
  4. SVG 2D入门4 - 笔画与填充
  5. Koala logoJava EE 应用开发平台 Koala
  6. 常用经典SQL语句大全(技巧)
  7. Server SAN:弄潮儿云计算时代
  8. SSIS从理论到实战,再到应用(1)----创建自己的第一个包
  9. Mac下MySQL的安装与配置
  10. nyoj_78:圈水池(凸包入门)
  11. iOS白名单设置
  12. 近期热门微信小程序demo源码下载汇总
  13. Http请求小结
  14. 回顾曾经的自己,献给java初学者的建议
  15. Ajax爬虫必用到的字典转换器
  16. VC++常用数据类型
  17. android 监听动画对象后不能播放动画
  18. ECharts配置项之title(标题)
  19. Redis集群部署及命令
  20. Spring AMQP 源码分析 02 - CachingConnectionFactory

热门文章

  1. 使用Socket.IO做单页SPA应用更新
  2. Qt无边框窗口的移动、拉伸边框、鼠标滚轮缩放大小
  3. Python实现字符串与数组相互转换功能示例
  4. 洛谷P3916 图的遍历
  5. 剑指offer——11旋转数组中最小的数字
  6. 转——调试寄存器 原理与使用:DR0-DR7
  7. 利用DNSQuery 进行DNS查询
  8. vue 父子组件传递数据
  9. windows下mysql8.0.x简单安装!
  10. soj考试2