luogu-HXOI-U331150-密室逃脱2

Horean0574 rp++

原题链接

Algorithms: 图论 最小生成树


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

那其实你就大错特错了!

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

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

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
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Edge {
int u, v, w;

bool operator < (const Edge &A) const {
return w < A.w;
}
};

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

int n, m, fa[N];
ll ans;
struct Edge e[M];

inline void init() {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
}

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

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

cin >> n;
init();
for (int i = 1; i <= n; ++i) {
int v;
cin >> v;
e[++m].u = 0;
e[m].v = i;
e[m].w = v;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int w;
cin >> w;
if (i != j) {
e[++m].u = i;
e[m].v = j;
e[m].w = w;
}
}
}

sort(e + 1, e + m + 1);
for (int i = 1; i <= m; ++i) {
int fu = find(e[i].u);
int fv = find(e[i].v);
if (fu != fv) {
fa[fu] = fv;
ans += e[i].w;
}
}

cout << ans;
}
  • Title: luogu-HXOI-U331150-密室逃脱2
  • Author: Horean0574
  • Created at : 2023-08-25 16:45:27
  • Updated at : 2023-09-01 19:51:10
  • Link: https://blog.hxrch.top/2023/08/25/luogu-HXOI-U331150-密室逃脱2/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
luogu-HXOI-U331150-密室逃脱2