题解 P4437 【[HNOI/AHOI2018]排列】
VenusM1nT
2020-10-07 16:05:31
~~这题的题解代码都好毒瘤啊~~
首先看到题目想到连边 $a_i\to i$，若有环则无解，否则构成一个森林，这一步可以用并查集直接判掉。
然后考虑求解，贪心取 权值/点数 最小的点，可以保证最后取到最大的值。这一步可以用堆来模拟。取完之后把这个点的数据加到它的父亲上，一步步取就做完了。
```cpp
#include<bits/stdc++.h>
#define N 500000
#define reg register
#define inl inline
#define int long long
using namespace std;
struct Node
{
int x,siz,w;
friend bool operator < (const Node &x,const Node &y)
{
return x.w*y.siz>x.siz*y.w;
}
};
priority_queue <Node> q;
int n,a[N+5],f[N+5],w[N+5],siz[N+5],ans;
int Find(reg int x)
{
return x==f[x]?x:f[x]=Find(f[x]);
}
signed main()
{
scanf("%lld",&n);
for(reg int i=0;i<=n;i++) f[i]=i;
for(reg int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
reg int x=Find(a[i]),y=Find(i);
if(x^y) f[x]=y;
else return puts("-1"),0;
}
for(reg int i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
q.push((Node){i,1,w[i]});
}
for(reg int i=0;i<=n;i++)
{
f[i]=i;
siz[i]=1;
}
while(!q.empty())
{
reg Node now=q.top();
q.pop();
reg int x=Find(now.x);
if(siz[x]^now.siz) continue;
reg int y=Find(a[x]);
f[x]=y;
ans+=w[x]*siz[y];
w[y]+=w[x];
siz[y]+=siz[x];
if(y) q.push((Node){y,siz[y],w[y]});
}
printf("%lld\n",ans);
return 0;
}
```