hduoj-kruscal最小生成树

发表于   |   分类于   |  

题目大意

　　http://acm.hdu.edu.cn/showproblem.php?pid=1233]

　　此题直接套用最小生成树的算法，这里采用基于并查集实现的Kruscal算法。

题目分析

　　并查集标准的操作：find，unite等，并查集要用路径压缩和rank函数进行优化。Kruscal算法要求先对所有边进行从小到大的排序，过多的不介绍了。

代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 10005
struct Edge {
    int src;
    int dest;
    int weight;
};
struct Edge e[MAX_SIZE];
int comp(const void* a, const void* b)
{
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}
int par[MAX_SIZE];
int rank2[MAX_SIZE];
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank2[i] = 0;
    }
}
int find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);//路径压缩
    }
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) {
        return;
    }
    if(rank2[x] < rank2[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if(rank2[x] == rank2[y]) {
            rank2[x]++;
        }
    }
    
}
bool same(int x, int y) {
    return find(x) == find(y);
}
int main() {
    int N, M;
    while(scanf("%d%d", &M, &N)) {
        if(M == 0) {
            return 0;
        }
        
        for(int m = 0; m < M; m++) {
            int s, d, w;
            scanf("%d%d%d", &s, &d, &w);
            e[m].src = s;
            e[m].dest = d;
            e[m].weight = w;
        }
        if(M < N - 1) {
            printf("?\n");
            continue;
        }
        //sort
        qsort(e, M, sizeof(struct Edge), comp);
        int ans = 0;
        int count = 0;
        init(N);
        for(int m = 0; m < M; m++) {
            if(same(e[m].src - 1, e[m].dest - 1)) {
                continue;
            }
            unite(e[m].src - 1, e[m].dest - 1);
            ans += e[m].weight;
            count++;
            if(count == N - 1) {
                break;
            }
        }
        int root = 0;
        for(int n = 0; n < N; n++) {
            if(par[n] == n) {
                root++;
            }
        }
        if(root > 1) {
            printf("?\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}