洛谷4437 [HNOI2018]排列

Luogu

BZOJ

分析

首先,如果 $a[j]=k$ ,那么 $k$ 一定在 $j$ 的前面。

考虑从 $a[j]$ 向 $j$ 连边,构成一个图。显然,如果有环的话是无解的,

那么现在就是,如果要选子节点,必须要先选父节点。$i$ 节点第 $T$ 个选出来的话,贡献是 $Tw[i]$ 。

考虑贪心。设当前权值最小的节点为 $i$。

  • 如果 $i$ 没有父节点的话,显然当前会选 $i$ 。
  • 如果 $i$ 有父节点,那么当 $i$ 的父节点选了之后一定会选 $i$,也就是说最后的排列中 $fa[i]$ 和 $i$ 挨在一起。

然后发现,多次合并后每个节点就代表一个序列。

考虑一个长度为 $l_1$ 的序列 $a$ 和一个长度为 $l_2$ 的序列 $b$ 。

经过一番推导得到,如果 $\frac{W_a}{l_1}<\frac{W_b}{l_2}$,那么拼成 $ab$ 会更优。

也就是说,平均权值小的点放前面会更优。

那么可以每次取出权值最小的点,然后将它与它的父节点合并。

计算答案的话,发现把 $b$ 接在 $a$ 后面会产生 $W_b\times l_a$ 的贡献,于是一边合并一边累加即可。

每次要取出一个最小值,可以用一个堆来维护。然后要资瓷堆内修改,可以随便拿个东西作为标记来解决。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,tot=0;
ll w[N];
int fa[N],f[N],sz[N],vis[N];

struct Edge { int v,nxt; } e[N];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

inline void dfs(int u) {
    vis[u]=1,++tot;
    for (re int i=head[u];i;i=e[i].nxt) {
        if (vis[e[i].v]) { puts("-1"); exit(0); }
        else dfs(e[i].v);
    }
}

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

struct node { int u,sz; ll w; };
bool operator <(node a,node b) { return a.w*b.sz>b.w*a.sz; }

priority_queue<node> Q;

int main() {
    n=read();
    for (re int i=1;i<=n;++i) fa[i]=read(),addEdge(fa[i],i);
    for (re int i=1;i<=n;++i) w[i]=read();
    dfs(0); if (tot<=n) { puts("-1"); return 0; }
    for (re int i=0;i<=n;++i) f[i]=i,sz[i]=1;
    for (re int i=1;i<=n;++i) Q.push((node){i,1,w[i]});
    ll ans=0;
    while (!Q.empty()) {
        node x=Q.top(); Q.pop();
        int u=find(x.u);
        if (sz[u]!=x.sz) continue;
        int p=find(fa[u]); f[u]=p;
        ans+=w[u]*sz[p],w[p]+=w[u],sz[p]+=sz[u];
        if (p) Q.push((node){p,sz[p],w[p]});
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 17 PM

6 条评论

  1. smy

    神仙M-sea什么时候做M-sea快跑啊QAQ

    1. M_sea
      @smy

      不是叫smy快跑吗qwq

  2. xgzc

    神仙M-sea什么时候做M-sea快跑啊QAQ

    1. M_sea
      @xgzc

      不是叫xgzc快跑吗qwq

  3. Itst

    神仙M-sea什么时候做M-sea快跑啊QAQ

    1. M_sea
      @Itst

      不是叫itst快跑吗qwq

发表评论