acwing-346. 走廊泼水节

发表于 分类于 阅读次数： Waline： 本文字数： 460 阅读时长 ≈ 2 分钟

考点

  • 最小生成树

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 6e3 + 50;
int n, fa[maxn], s[maxn];

struct node {
  int x_, y_, z_;
  bool operator<(node &a) { return z_ < a.z_; }
} e[maxn];

int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}

void kruskal() {
  sort(e + 1, e + n);
  ll ans = 0;
  for (int i = 1; i < n; ++i) {
    int x = find(e[i].x_), y = find(e[i].y_);
    if (x == y) continue;
    ans += ((ll)s[x] * s[y] - 1) * (e[i].z_ + 1);
    fa[y] = x;
    s[x] += s[y];
  }
  cout << ans << endl;
}

int main() {
  int t, x, y, z;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 1; i <= n; ++i) fa[i] = i, s[i] = 1;
    for (int i = 1; i < n; ++i) {
      cin >> x >> y >> z;
      e[i] = {x, y, z};
    }
    kruskal();
  }
  return 0;
}

思路

完全图代表节点两两都有边。

把这n - 1条边按照权值从小到大排序，依次扫描每个边，执行一个类似Kruskal的算法。

随后考察的是对Kruskal的流程掌握：

  1. 初始时，每个点都是一个只有它自己的集合
  2. 寻找所有集合彼此之间（集合内部忽略）边权最小的边，将这条最小边的两端点所在集合合并，成为一个新集合
  3. 重复2

如图所示，Sx和Sy两个集合内部已经是完全图，且内部所有边权必大于DE。

现根据DE边进行合并，DE边权为z。

以点C为例子，显然需要新增的CF、CE、CG三条边的边权最小为z + 1；

如果为z甚至更小，那么DE边就不是两集合合并的唯一可选项，这与唯一性矛盾。

根据乘法原理，两集合合并需要新增的边数为\(\left| S_x \right|\times \left| S_y \right|-1\)，去掉了DE边；新增边权均为z + 1

得到最小边权总和\(\left( z+1 \right) \times \left( \left| S_x \right|\times \left| S_y \right|-1 \right)\)