数据结构实验之图论六：村村通公路——最小生成树Kruskal算法

矫情吗；* 2022-06-12 03:17 226阅读 0赞

Think:  
1知识点：最小生成树Kruskal算法（并查集思想）  
2反思：注意变量初始化

[SDUT题目链接][SDUT]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    struct node {
        int u;
        int v;
        int w;
    }e[1004];
    
    int n, f[1004];
    
    void Init();
    int get_f(int v);
    bool Merge(int u, int v);
    
    bool cmp(struct node a, struct node b){
        return (a.w < b.w);
    }
    
    int main(){
        int m, i, cnt, sum;
        while(scanf("%d %d", &n, &m) != EOF){
            Init();
            for(i = 1; i <= m; i++){
                scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
            }
            sort(e+1, e+m+1, cmp);
            cnt = 0, sum = 0;///初始化
            for(i = 1; i <= m; i++){
                if(cnt == n-1)
                    break;
                if(!Merge(e[i].u, e[i].v)){
                    sum += e[i].w;
                    cnt++;
                }
            }
            if(cnt == n-1){
                printf("%d\n", sum);
            }
            else {
                printf("-1\n");
            }
        }
        return 0;
    }
    void Init(){
        for(int i = 1; i <= n; i++)
            f[i] = i;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        else {
            f[v] = get_f(f[v]);
            return f[v];
        }
    }
    bool Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 == t2){
            return true;
        }
        else {
            f[t2] = t1;
            return false;
        }
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 236KB
    Submit time: 2017-07-14 09:44:16
    ****************************************************/

[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3362.html