[HNOI2018]排列

Description：

给定 \(n\) 个整数 \(a_1, a_2, \dots, a_n, 0 \le a_i \le n\)，以及 \(n\) 个整数 \(w_1, w_2, \dots, w_n\)。称 \(a_1, a_2, \dots, a_n\)的 一个排列 \(a_{p[1]}, a_{p[2]}, \dots, a_{p[n]}\)为 \(a_1, a_2, \dots, a_n\)的一个合法排列，当且仅当该排列满足：对于任意 的 \(k\) 和任意的 \(j\)，如果 \(j \le k\)，那么 \(a_{p[j]}\)不等于 \(p[k]\)。（换句话说就是：对于任意的 \(k\) 和任意的 \(j\)，如果 \(p[k]\)等于 \(a_{ p[j] }\)，那么 $k<j $ 。）定义这个合法排列的权值为 ​\(w_{p[1]} + 2w_{p[2]} + \dots + nw_{p[n]}\)。

Hint：

\(n \le 5*10^5\)

Solution:

估计很多人是因为看不懂题意才做不出来的。。。

。。。题面真的反人类

如果 \(p[k]\)等于 \(a_{ p[j] }\)，那么 $ k<j $

换个说法：

如果 \(p[k]=a_{p[j]}\) 那么 \(k<j\)

即 \(y=a_x\) 且\(y\) 排在 \(x\)前面

又\(a_x=a_x\)

考虑拓扑排序，连边 \(a_x->x\)

这样每个点入度为1

连边后一定是一颗以0为根的树

为什么？因为\(a \in [1,n]\) ,而\(a_i \in [0,n]\)

若图中只有\(n\)个点,那么由于有\(n\)条边

一定成环

所有\(0\)必然为起点

如果有环，则无法满足限制说明合法排列不存在

接下来考虑在树上贪心

每次找到最小的权值\(w_i\),若此时\(fa[i]=0\),则可直接选\(i\)

否则需要把\(w_i​\)合并到\(fa[i]​\)上,等待\(fa[i]​\)选完再选

但有一个问题,这样操作后每个点变成了序列,如何比较优劣?

考虑 $ 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}​\)也就是平均权值小的放前面答案会更优

这里使用 稍加修改的堆+并查集 实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=5e5+5;
int n,cnt,tot,f[mxn],s[mxn],hd[mxn],vis[mxn],anc[mxn];
ll ans,w[mxn];

struct ed {
    int to,nxt;
}t[mxn<<1];

struct data {
    int id,sz;
    ll val;
    friend bool operator < (data a,data b) {
        return a.val*b.sz>b.val*a.sz; //按平均值排序
    }
}tp;

priority_queue<data > q;

inline void add(int u,int v) {
    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

int find(int x) {
    return anc[x]==x?x:anc[x]=find(anc[x]);
}

void dfs(int u,int fa) {
    vis[u]=1; ++tot;
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa) continue ;
        if(vis[v]) {
            puts("-1");
            exit(0);
        }
        dfs(v,u);
    }
}

int main()
{
    scanf("%d",&n); s[0]=1; //别忘记赋初值
    for(int i=1;i<=n;++i) {
        scanf("%d",&f[i]);
        add(f[i],i); anc[i]=i,s[i]=1;
    }
    dfs(0,-1); if(tot<n) {puts("-1"); return 0;}
    for(int i=1;i<=n;++i) {
        scanf("%lld",&w[i]);
        q.push((data){i,1,w[i]});
    }
    while(!q.empty()) {
        tp=q.top(); q.pop(); int u=find(tp.id);
        if(s[u]!=tp.sz) continue ;/*已经有合并后新的节点,丢弃以前的*/ anc[u]=find(f[u]); 
        ans+=w[u]*s[anc[u]],s[anc[u]]+=s[u],w[anc[u]]+=w[u]; //每次先计算贡献,再合并
        if(anc[u]) q.push((data){anc[u],s[anc[u]],w[anc[u]]});
    }
    printf("%lld",ans);
    return 0;
}