HNOI2018 排列

link

给定 ,定义一个 排列(设ii的位置为pip_i,且p0=0p_0=0)是合法的当且仅当ipai<pi\forall_i p_{a_i}<p_i

定义一个排列的权值为wipi\sum w_ip_i,求合法排列中权值的最大值。

题解

模型转化

对于pai<pip_{a_i}<p_i的限制,连一条ai,ia_i,i的边。

如果出现了环则无解,否则一定是形成了一个以0为根n+1点的树。

然后就是poj2054原题了。

做法

由于我们希望最后权值尽量大,所以就希望wiw_i小的靠前选择。

当你选出wiw_i最小的i,i一定尽量在父亲之后选择。

这样就形成了一个"联通块"

考虑两个联通块的优先顺序:

设两个联通块的权值和和点数分别是w1,s1,w2,s2w_1,s_1,w_2,s_2,那么1在2前面需要s1w2w1s2s_1w_2\ge w_1s_2,也就是w1s1w2s2\frac{w_1}{s_1}\le \frac{w_2}{s_2}

所以对于一个联通块,直接按平均权值当做一个点就可以了。

以及每次选出一个联通块A时(A的父亲的联通块是F),对答案的贡献就是wAsFw_As_F(在F所在联通块全部选完再选A的联通块)。

这就完了。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*
Author: CNYALI_LK
LANG: C++
PROG: 4437.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define mp3(a,b,c) make_pair((long double)(a)/b,c)
using namespace std;
typedef long long ll;
typedef pair<long double,ll> pii;
typedef pair<pii,ll> piii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll fa[500005],w[500005],bel[500005],siz[500005];
ll belong(ll x){return x==bel[x]?x:bel[x]=belong(bel[x]);}

__gnu_pbds::priority_queue<pii,greater<pii> >p;
__gnu_pbds::priority_queue<pii,greater<pii> >::point_iterator it[500005];
int main(){
#ifdef cnyali_lk
freopen("4437.in","r",stdin);
freopen("4437.out","w",stdout);
#endif
ll n;
read(n);
for(ll i=1;i<=n;++i)bel[i]=i;
for(ll i=1;i<=n;++i){read(fa[i]);if(belong(i)==belong(fa[i])){write("-1\n");return 0;}bel[belong(i)]=belong(fa[i]);}
for(ll i=1;i<=n;++i)bel[i]=i;
bel[0]=0;
it[0]=p.push(mp3(1e18,1,0LL));
for(ll i=1;i<=n;++i){
read(w[i]);
it[i]=p.push(mp3(w[i],1,i));
siz[i]=1;
}

w[0]=1e18;
siz[0]=1;
ll ans=0;
for(;n;--n){
pii a=p.top();
p.pop();
ll f=belong(fa[a.y]);
ans+=w[a.y]*siz[f];
siz[f]+=siz[a.y];
w[f]+=w[a.y];
bel[a.y]=f;
p.modify(it[f],mp3(w[f],siz[f],f));
}
printf("%lld\n",ans);
return 0;
}
文章目录
  1. 1. 题解
    1. 1.1. 模型转化
    2. 1.2. 做法
|

博客使用Disqus作为评论系统