题解 P4437 【[HNOI/AHOI2018]排列】

· · 题解

题意

给你一个序列a

定义a的一个排列p合法需要满足当p[j]\le p[k]时不存在a_{p[j]}=p[k]

定义一个排列的权值是\sum_{i=1}^n iw_{p[i]}

求最大权值

你永远不会想到会在正式考试上看到原题,而且还在某校集训上讲过???

原题链接Poj2054

题解

考虑转化

考虑到如果a_j=k那么k一定要排在j前面

可以理解为对于j来说k需要先选

考虑建出一个图,连边k=a_j\to j方向表示顺序

这样[1,n]每个点的入度都会是1

如果有环那么就无解,否则这个图就是一棵以0为根树

如果是在树上的话,也就是说必须要先选父亲才能选儿子

对于一个点i,如果选到他的时间是T也就是说他在排列中的位置是T,那么他的贡献就是Tw_i

这样我们就成功把这道题转化成那个原题了但是这并没有什么用

考虑怎么求最大值

考虑一种贪心

考虑一个当前权值最小的点i

1.$如果$i$没有父亲$(fa[i]=0),$那么我们当前一定是选$i 2.$如果$i$有父亲$,$那么当$fa[i]$选了后我们一定会最先选$i

也就是说在最后的排列中fa[i]和i是挨在一块的

但是考虑到实际上多次合并后每个节点就是一个序列

考虑一个长度为m_1的序列a和一个长度为m_2的序列b

考虑ab和ba两种合并后的序列的答案(假设当前在第i位)

W_{ab}=\sum_{j=1}^{m_1}(i+j)w_{a_j}+\sum_{j=1}^{m_2}(i+j+m_1)w_{b_j} W_{ba}=\sum_{j=1}^{m_2}(i+j)w_{b_j}+\sum_{j=1}^{m_1}(i+j+m_2)w_{a_j} W_{ab}-W_{ba}=m_1W_b-m_2W_a

如果W_{ab}\gt W_{ba}\Rightarrow \frac{W_a}{m_1}\lt\frac{W_b}{m_2}

也就是平均权值小的放前面答案会更优

那么我们把平均权值作为合并后的新权值继续操作即可

计算答案的话就把答案拆开来计算

根据上面的式子可以得到把一个序列b放在一个序列a后面会产生独立的W_b\times m_1的贡献,边合并边求和就好了

每次取最小可以用堆实现

因为要修改权值所以你可以用set

你可以用pb\_ds里面的带修改堆,或者你拿个东西做标记就好了

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=5e5+5;
typedef int arr[N];
typedef long long ll;
struct Da{
    int u,sz;ll w;
    inline bool operator<(const Da b)const{return w*b.sz>b.w*sz;}
};
struct eg{int nx,to;}e[N];
int n,Cnt;arr fi,fa,Fa,sz,vis;ll ans,w[N];priority_queue<Da>q;
void dfs(int u){vis[u]=1;++Cnt;go(u)if(vis[v]){puts("-1"),exit(0);}else dfs(v);}
inline void add(int u,int v){static int ce=0;e[++ce]={fi[u],v},fi[u]=ce;}
int gf(int x){return Fa[x]==x?x:Fa[x]=gf(Fa[x]);}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n);
    fp(i,1,n)sd(fa[i]),add(fa[i],i);
    dfs(0);if(Cnt<=n)return puts("-1"),0;
    fp(i,0,n)Fa[i]=i,sz[i]=1;
    fp(i,1,n)sd(w[i]),q.push(Da{i,1,w[i]});
    int u,p;Da s;
    while(!q.empty()){
        s=q.top();q.pop();
        if(sz[u=gf(s.u)]^s.sz)continue;
        Fa[u]=p=gf(fa[u]);
        ans+=w[u]*sz[p],w[p]+=w[u],sz[p]+=sz[u];
        if(p)q.push(Da{p,sz[p],w[p]});
    }
    printf("%lld\n",ans);
return 0;
}