杭电多校8 07
Darnassus
题目链接
题目大意
给定一个长度为\(n\)的序列\(a\),是有\(1-n\)的排列组成，连接\(i j\)两个点的代价为\(abs(i - j) * abs(a[i] - a[j])\)，求其最小生成树。
题解
我们发现，若将所有相邻的边连起来，每条边的边权都小于\(n-1\)，因此最后的最小生成树边权和一定小于\((n-1)^2\)
于是最小生成树的每条边一定小于\(n-1\)
我们只需要找到所有的这样的边，然后进行kruskal就行
由于边数过多，这里需要采取桶排的思想
代码
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 | #include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 3e7 + 10;
int pre[N];
struct node_ {
int a, b;
};
int head[50004], ne[N];
node_ e[N];
int idx = 0;
inline int find(int x) {
return x == pre[x] ? pre[x] : pre[x] = find(pre[x]);
}
void add(int a, node_ b) {
e[idx] = b;
ne[idx] = head[a];
head[a] = idx ++ ;
}
int p[50004], pos[50004];
int cnt = 0;
int res = 0;
void init(int n) {
for(int i = 1; i <= n; i ++ ) pre[i] = i;
}
void kruskal(int n) {
int res = 0;
int cnt = 0;
for(int i = 1; i <= n - 1; i ++ ) {
for(int j = head[i]; j != -1; j = ne[j]) {
int a = e[j].a;
int b = e[j].b;
int fx = find(a);
int fy = find(b);
if(fx != fy) {
pre[fx] = fy;
res += i;
cnt ++;
}
if (cnt == n - 1) break;
}
if (cnt == n - 1) break;
}
printf("%lld\n", res);
}
int main() {
int t;
scanf("%d", &t);
while(t -- ) {
int n;
memset(head, -1, sizeof(head));
idx = 0;
scanf("%d", &n);
init(n);
for(int i = 1; i <= n; i ++ ) {
int k;
scanf("%d", &p[i]);
pos[p[i]] = i;
}
cnt = 0;
for(int i = 1; i <= n; i ++ ) {
for(int j = 1; i + j <= n; j ++ ) {
if(abs(p[i] - p[i + j]) * j <= n && abs(p[i] - p[i + j]) * j > 0) {
add(j * abs(p[i] - p[i + j]), {i, i + j});
}
if(j * abs(pos[i + j] - pos[i]) <= n && j * abs(pos[i + j] - pos[i]) > 0) {
add(j * abs(pos[i + j] - pos[i]), {pos[i + j], pos[i]});
}
}
}
kruskal(n);
}
}
|