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