翻车笔记_ vijos1579 宿命的PSS [清奇脑回路, Kruskal] [脑回路训练合集]

又是一个清奇的脑回路, 也考验对算法的理解深度

懵逼的 题目

传送至 Vijos

扯淡的 题解

只会打$n ^ 2$暴力, 剩下啥都不会了

首先考虑Kruskal选一条边的时候, 条件是 [当前边的两个顶点不在一个连通分量里, 而且这一条边是连接两个连通分量的权值最小的边] 所以当我们得知了一条最小生成树的边时, 我们就知道, 这两个连通分量之间所有的连边都要比这条边大, 所以我们可以:

  • 按边的权值从小到大排序, 因为Kruskal是从小到大, 我们要根据Kruskal推出答案
  • 对于当前的这条边, 找到两个顶点所属的连通分量的大小, 相乘即为这两个连通分量之间要连的边
  • 合并这两个连通分量
    没了

沙茶的 代码

60分大暴力

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
//暴力

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (20000 + 5)
#define LL long long
using namespace std;
struct edg
{
int from;
int to;
int cost;
int next;
} b[MAXN << 1];
int cntb;
int g[MAXN];
int n;
LL ans;
int fa[MAXN];
void solve();
void dfs(int, int, bool);
void adn(int, int, int);
int main()
{
scanf("%d", &n);
int srx, sry, srz;
for (int i = 1; i < n; i++)
{
scanf("%d%d%d", &srx, &sry, &srz);
adn(srx, sry, srz);
adn(sry, srx, srz);
}
solve();
ans >>= 1;
printf("%lld", ans);
return 0;
}
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
void solve()
{
for (int i = 1; i <= n; i++)
{
memset(fa, 0, sizeof(fa));
for (int j = g[i]; j; j = b[j].next)
{
fa[b[j].to] = i;
dfs(b[j].to, b[j].cost, true);
}
}
}
void dfs(int dq, int dqmax, bool sf)
{
ans += dqmax;
ans += (sf ? 0 : 1);
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].to != fa[dq])
{
fa[b[i].to] = dq;
dfs(b[i].to, max(dqmax, b[i].cost), false);
}
}
}

AC

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
// Vijos1579改

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (20000 + 5)
#define LL long long
using namespace std;
struct edg
{
int from;
int to;
LL cost;
}b[MAXN];
int n;
LL ans;
int rak[MAXN];
int fa[MAXN];
bool cmp(edg, edg);
void solve();
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
scanf("%d%d%d", &b[i].from, &b[i].to, &b[i].cost);
}
solve();
ans -= (n - 1);
printf("%lld", ans);
return 0;
}
bool cmp(edg x, edg y)
{
return x.cost < y.cost;
}
int find(int x)
{
return x == fa[x] ? (x) : (fa[x] = find(fa[x]));
}
void uni(int x, int y)
{
int fx = find(x);
int fy = find(y);
rak[fx] += rak[fy];
fa[fy] = fx;
}
void solve()
{
sort(b + 1, b + n, cmp);
for (int i = 1; i <= n; i++)
{
fa[i] = i;
rak[i] = 1;
}
for (int i = 1; i < n; i++)
{
int x = b[i].from;
int y = b[i].to;
int fx = find(x);
int fy = find(y);
ans += (LL) rak[fx] * rak[fy] * (b[i].cost + 1);
uni(x, y);
}
}

/*
4
1 2 1
1 3 1
1 4 2

*/
/*
3
1 2 4
2 3 7

*/

By 没写作业被D飞的 Cansult