图结构练习——最小生成树

淩亂°似流年 2022-06-12 03:19 162阅读 0赞

Think:  
1知识点：最小生成树Kruskal算法  
2反思：题意分析建议使用最小生成树Prim算法  
3知识体系分析：Kruskal算法更适用于稀疏图，未加堆优化的Prim算法更适用于稠密图，堆优化的Prim算法更适用于稀疏图——啊哈！算法

[SDUT题目链接][SDUT]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    struct node {
        int u;
        int v;
        int w;
    }e[100004];
    
    int n, f[104];
    
    bool cmp(struct node a, struct node b){
        return (a.w < b.w);
    }
    
    void Init();
    int get_f(int v);
    bool Merge(int u, int v);
    
    int main(){
        int m, i, cnt, sum;
        while(scanf("%d %d", &n, &m) != EOF){
            cnt = sum = 0;
            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);
            for(i = 1; i <= m; i++){
                if(cnt == n-1)
                    break;
                if(!Merge(e[i].u, e[i].v)){
                    cnt++;
                    sum += e[i].w;
                }
            }
    
            printf("%d\n", sum);
        }
        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: 20ms
    Take Memory: 336KB
    Submit time: 2017-07-14 10:15:57
    ****************************************************/

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