luogu-HXOI-U331150-密室逃脱2

归档 26

数学 11 开发 6 题解 5 生活 3 作文篇章 1

426 字

2 分钟

luogu-HXOI-U331150-密室逃脱2

2023-08-25

2023-09-01

题解

HXOI

图论

最小生成树

浏览量加载中...

原题链接

Algorithms: 图论 最小生成树

不要看题面花里胡哨的，实际上它意思已经很明确了，就是让你在若干个站点存放 能量补给用具，使得能量能够扩散到图内每个站点。说到这里应该有些同学觉得，那我存放一个 能量补给用具 不就行了吗，这应该都能联通到每个站点啊。

警告

那其实你就大错特错了！

因为它还是要考虑消耗的体力最小啊，那这怎么办……

这时候就需要用上我们的最小生成树了！其实这道题只需要多建一个 0号虚拟节点，与其他各个节点相连，就不用考虑每个站点的消耗了，然后再跑一遍 $Kruskal$ 模板，就可以了。

$Std$

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
typedef long long ll;
7

8
struct Edge {
9
  int u, v, w;
10

11
  bool operator < (const Edge &A) const {
12
    return w < A.w;
13
  }
14
};
15

16
const int N = 2e3 + 5;
17
const int M = N * (N - 1);
18

19
int n, m, fa[N];
20
ll ans;
21
struct Edge e[M];
22

23
inline void init() {
24
  for (int i = 1; i <= n; ++i) {
25
    fa[i] = i;
26
  }
27
}
28

29
inline int find(const int &x) {
30
  return fa[x] == x ? x : fa[x] = find(fa[x]);
31
}
32

33
int main() {
34
  ios::sync_with_stdio(false);
35
  cin.tie(nullptr), cout.tie(nullptr);
36

37
  cin >> n;
38
  init();
39
  for (int i = 1; i <= n; ++i) {
40
    int v;
41
    cin >> v;
42
    e[++m].u = 0;
43
    e[m].v = i;
44
    e[m].w = v;
45
  }
46
  for (int i = 1; i <= n; ++i) {
47
    for (int j = 1; j <= n; ++j) {
48
      int w;
49
      cin >> w;
50
      if (i != j) {
51
        e[++m].u = i;
52
        e[m].v = j;
53
        e[m].w = w;
54
      }
55
    }
56
  }
57

58
  sort(e + 1, e + m + 1);
59
  for (int i = 1; i <= m; ++i) {
60
    int fu = find(e[i].u);
61
    int fv = find(e[i].v);
62
    if (fu != fv) {
63
      fa[fu] = fv;
64
      ans += e[i].w;
65
    }
66
  }
67

68
  cout << ans;
69
}