hihoCoder菗1098最小生成樹二・Kruscalアルゴリズム
7295 ワード
本題の住所
以前Kruscalアルゴリズムを書いたことがありませんが、書いてみたらPrimeアルゴリズムよりずっと簡単になったと分かりました.
そして、検索集の応用はあまりにも古典的です.
コード:
以前Kruscalアルゴリズムを書いたことがありませんが、書いてみたらPrimeアルゴリズムよりずっと簡単になったと分かりました.
そして、検索集の応用はあまりにも古典的です.
コード:
1 #include <iostream>
2 #include <cstdlib>
3
4 using namespace std;
5
6 #define MAX_EDGE 1000008
7 #define MAX_POINT 100008
8
9 struct Edge {
10 int a;
11 int b;
12 int len;
13 };
14
15 int mycmp(const void *a, const void *b) {
16 Edge *pa = (Edge *) a;
17 Edge *pb = (Edge *) b;
18 return pa->len - pb->len;
19 }
20
21 int N, M;
22 Edge e[MAX_EDGE];
23 int p[MAX_POINT];
24
25 int find(int i) {
26 if (p[i] == i)
27 return i;
28 return p[i] = find(p[i]);
29 }
30
31 void merge(int i, int j) {
32 int pi = find(i);
33 int pj = find(j);
34 p[pi] = pj;
35 }
36
37 int kruscal() {
38 int res = 0;
39
40 qsort(e, M, sizeof(Edge), mycmp);
41 for (int i = 0; i < M; i++) {
42 if (find(e[i].a) == find(e[i].b))
43 continue;
44 res += e[i].len;
45 merge(e[i].a, e[i].b);
46 }
47
48 return res;
49 }
50
51 int main() {
52 scanf("%d%d", &N, &M);
53 for (int i = 1; i <= N; i++)
54 p[i] = i;
55 for (int i = 0; i < M; i++)
56 scanf("%d%d%d", &(e[i].a), &(e[i].b), &(e[i].len));
57
58 printf("%d
", kruscal());
59 return 0;
60 }