P4437 [HNOI/AHOI2018]排列

考虑这个限制本质上就是限制了 $i$ 在 $a_i$ 后被选,也就是如果从 $i$ 向 $a_i$ 连边,然后就是必须先选择祖先再选择儿子的一个选择点的问题,使得最后 $\sum{iA_i}$ 尽量大。如果存在环,显然无解。

我们考虑全局最小的点,我们显然可以把它合并到它的父亲上,因为在选择它的父亲后选择这个点本身一定是最优的决策。如果一直合并,我们会得到很多的联通块。但是如何确定两个块谁先被合并?我们考虑合并 $W,V$ 的代价:

考虑下面大于上面,也就是说先选择 $u$ 更优秀,那么

也就是

按照这个东西贪心,拿堆维护即可。

最后所有东西都会被合并到 $0$ 上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 1000000007
int n , k;
int f[MAXN] , w[MAXN] , cnt;
struct node {
ll w; int m , idx; ll as; int tim = 0;
node( ll w = 0 , int m = 0 , int idx = 0 , ll as = 0 , int tm = 0 ) : w(w) , m(m) , idx(idx) , as(as) , tim(tm) {}
bool operator < ( node x ) const {
return 1ll * w * x.m > 1ll * x.w * m;
}
node operator + ( node x ) {
return node( x.w + w , m + x.m , idx , as + x.as + x.w * 1ll * m , ++ cnt );
}
} nd[MAXN] ;
priority_queue<node> Q;

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

void solve( ) {
cin >> n;
rep( i , 1 , n ) fa[i] = i;
rep( i , 1 , n ) {
scanf("%d",&f[i]);
if( find( i ) == find( f[i] ) ) puts("-1") , exit(0);
else {
fa[find( i )] = find( f[i] );
}
}
rep( i , 1 , n ) fa[i] = i;
rep( i , 1 , n ) {
scanf("%d",w + i);
Q.push( nd[i] = (node) { w[i] , 1 , i , w[i] , 0 } );
}
while( !Q.empty() ) {
node tp = Q.top(); Q.pop();
if( nd[tp.idx].tim != tp.tim ) continue;
int x = find( f[tp.idx] );
fa[tp.idx] = x;
nd[x] = nd[x] + tp;
if( x ) Q.push( nd[x] );
}
printf("%lld\n",nd[0].as);
}

signed main() {
// freopen("perm6.in","r",stdin);
// freopen("fuckout","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2020/11/18/p4437-hnoiahoi2018pai-lie/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog