Slim Span UVA - 1395 ——Kruskal算法生成最小树

待我称王封你为后i 2022-06-15 06:57 187阅读 0赞

Think:  
1Kruskal算法生成最小树  
2题意理解:  
1>生成一颗最小树使得他的边的最大权值减去边的最小权值最小  
3思路:从权值最小的边出发建立最小生成树，不断更新生成的最小树的苗条度(边的最大权值减去边的最小权值)

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct node {
        int a, b;
        int w;
    }edg[5400];
    
    bool cmp(node a, node b){
        return a.w < b.w;
    }
    
    int n, m, f[144];
    
    void Init();
    bool merge(int u, int v);
    int get_f(int x);
    
    int main(){
        int i, j, ans, cnt, sum;
        bool flag;
        while(scanf("%d %d", &n, &m) && (n || m)){
            for(i = 1; i <= m; i++)
                scanf("%d %d %d", &edg[i].a, &edg[i].b, &edg[i].w);
            sort(edg+1, edg+m+1, cmp);
            ans = 19980414;
            for(i = 1; i <= m; i++){
                Init();
                cnt = 0, flag = false;
                for(j = i; j <= m; j++){
                    if(merge(edg[j].a, edg[j].b)){
                        cnt++;
                    }
                    if(cnt == n-1){
                        sum = edg[j].w - edg[i].w;
                        ans = min(ans, sum);
                        flag = true;
                        break;
                    }
                }
                if(!flag)
                    break;
            }
            if(ans != 19980414) printf("%d\n", ans);
            else printf("-1\n");
        }
        return 0;
    }
    void Init(){
        for(int i = 1; i <= n; i++)
            f[i] = i;
    }
    bool merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 != t2){
            f[t2] = t1;
            return true;
        }
        else return false;
    }
    int get_f(int x){
        if(f[x] == x)
            return x;
        else {
            f[x] = get_f(f[x]);
            return f[x];
        }
    }

[vjudge]: https://vjudge.net/problem/UVA-1395