「HNOI2018」排列 - 贪心 + 堆 + 并查集

给你一个序列aa

定义aa的一个排列pp合法需要满足当pjpkp_j\le p_k时不存在apj=pka_{p_j}=p_k

定义一个排列的权值是iwpi\sum i*w_{p_i}

求最大权值

1n500000,0ain,1wi109,wi1.5×10131\le n \le 500000,0 \le a_i \le n,1 \le w_i \le 10^9 ,\sum w_i \le 1.5\times10^{13}

Luogu P4437

Solution

首先可以发现,若aj=ka_j=k,则kk一定要排在jj之前

所以把所有ajja_j \rightarrow j连边,最后的图如果有环则无解,否则就是一颗树

那么题目转化为一棵树,按照某种顺序 p1,...,pnp_1 , ..., p_n 依次选取所有点, 满足每个点的父亲比自己先选, 在此基础上最大化 iwpi\sum i * w_{p_i}.

考虑直接贪心,对于当前剩余权值最小的点,,选了它的父亲后一定马上就会选它

这样的话也就相当于把两个连通块合并,设分别为i,ji,j,那么iijj优则需要满足

wileni+wj(leni+lenj>wjsj+wi(leni+lenj)w_i*len_i+w_j*(len_i+len_j > w_j * s_j + w_i * (len_i + len_j)ww表示该连通块中所有点权值和,lenlen表示点数)

wileni<wjlenj\frac{w_i}{len_i} < \frac{w_j}{len_j}对​

因此按照wileni\frac{w_i}{len_i}从小到大选,用可删除堆+并查集维护即可

Code

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

inline int read ()
{
int sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int Maxn = 5e5 + 100;

int N, A[Maxn], W[Maxn];
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int Vis[Maxn], cnt;

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

inline void dfs (int x)
{
if (Vis[x]) { puts("-1"); exit(0); }
++cnt;
Vis[x] = 1;
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
dfs(y);
}
}

struct node
{
LL w, len;
int id;
inline int operator < (const node &a) const
{
if (a.w * len == w * a.len) return a.id < id;
return a.w * len < w * a.len;
}
inline int operator == (const node &a) const
{
return ((a.w == w) && (a.len == len) && (a.id == id));
}
};

struct Heap
{
priority_queue <node> a, b;

inline void del () { while (!b.empty() && a.top() == b.top()) a.pop(), b.pop(); }

inline void pop () { del(); a.pop(); }

inline void erase (node k) { b.push(k); }

inline node top () { del(); return a.top(); }

inline int empty () { del(); return a.empty(); }

inline void push (node k) { a.push(k); }
}Q;

LL ans;

namespace DSU
{
int fa[Maxn];
LL w[Maxn], len[Maxn];
inline void init () { for (int i = 1; i <= N; ++i) fa[i] = i, w[i] = W[i], len[i] = 1, Q.push((node){w[i], len[i], i}); }

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

inline void link (int x, int y)
{
if (y) Q.erase((node){w[y], len[y], y});
ans += w[x] * len[y];
w[y] += w[x], len[y] += len[x], fa[x] = y;
/**/ w[x] = len[x] = 0;
if (y) Q.push((node){w[y], len[y], y});
}
}

inline void Solve ()
{
dfs(0);
if (cnt <= N) { puts("-1"); return ; }

DSU :: init();
/**/while (!Q.empty())
{
int x = Q.top().id, y = DSU :: find(A[x]); Q.pop();
DSU :: link (x, y);
}
cout<<ans<<endl;
}

inline void Input ()
{
N = read();
for (int i = 1; i <= N; ++i) A[i] = read(), add_edge (A[i], i);
for (int i = 1; i <= N; ++i) ans += (W[i] = read());
}

int main()
{
#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
Input();
Solve();
return 0;
}
感谢你的赞赏!