今天我刷题了吗
搜索文档…
Kruskal 算法
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(5e3 + 10);
7
const int maxm(2e5 + 10);
8
int pre[maxn];
9
10
struct edge {
11
int u, v, w;
12
} edges[maxm];
13
14
template<typename T = int>
15
inline const T read()
16
{
17
T x = 0, f = 1;
18
char ch = getchar();
19
while (ch < '0' or ch > '9') {
20
if (ch == '-') f = -1;
21
ch = getchar();
22
}
23
while (ch >= '0' and ch <= '9') {
24
x = (x << 3) + (x << 1) + ch - '0';
25
ch = getchar();
26
}
27
return x * f;
28
}
29
30
template<typename T>
31
inline void write(T x, bool ln)
32
{
33
if (x < 0) {
34
putchar('-');
35
x = -x;
36
}
37
if (x > 9) write(x / 10, false);
38
putchar(x % 10 + '0');
39
if (ln) putchar(10);
40
}
41
42
inline int Find(int cur)
43
{
44
return pre[cur] == cur ? cur : pre[cur] = Find(pre[cur]);
45
}
46
47
inline void Union(int u, int v)
48
{
49
pre[Find(v)] = Find(u);
50
}
51
52
int kruskal(int n, int m)
53
{
54
int sum = 0, cnt = 0;
55
for (int i = 0; i < m and cnt < n - 1; ++i) {
56
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
57
if (Find(u) not_eq Find(v)) {
58
Union(u, v);
59
++cnt;
60
sum += w;
61
}
62
}
63
return cnt == n - 1 ? sum : -1;
64
}
65
66
int main()
67
{
68
#ifndef ONLINE_JUDGE
69
freopen("input.txt", "r", stdin);
70
#endif
71
int n = read(), m = read();
72
for (int i = 1; i <= n; ++i) {
73
pre[i] = i;
74
}
75
for (int i = 0; i < m; ++i) {
76
edges[i].u = read();
77
edges[i].v = read();
78
edges[i].w = read();
79
}
80
sort(edges, edges + m, [&](const edge& a, const edge& b) {
81
return a.w < b.w;
82
});
83
int res = kruskal(n, m);
84
if (compl res) {
85
write(res, true);
86
} else {
87
puts("orz");
88
}
89
return 0;
90
}
Copied!
最近更新 11mo ago
复制链接