[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}ltfrac{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;
}