最小生成树-克鲁斯卡尔模板

红太狼 2021-03-25 14:46 536阅读 0赞

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int fat[5001];
    int tot;
    struct node{
        int x,y,z;//结构体保存起点x，终点y，以及边权z
    }f[200001];
    int find(int x)//路径压缩
    {
        if(fat[x] != x) 
            fat[x] = find(fat[x]);
        return fat[x];
    }
    void unionn(int x,int y)//合并
    {
        int x1=find(x),y1=find(y);
        fat[y1]=x1;
    }
    bool cmp(node a,node b)
    {
        return a.z<b.z;//快排的规则
    }
    int main()
    {
        int m,n;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);
    
        for(int i=1;i<=n;i++) fat[i]=i;//自己叫自己爸爸
    
        sort(f+1,f+m+1,cmp);//快排
    
        int k=0;//计数
    
        for(int i=1;i<=m;i++)
        {
            if(find(f[i].x)!=find(f[i].y))//不在同一集合内
            {
    
                unionn(f[i].x,f[i].y);
    
                tot+=f[i].z;//计算权值和
    
                k++;
            }
        }
        if(k<n-1) printf("orz");//判断是否连通
    
        else printf("%d",tot);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，536人围观）

还没有评论，来说两句吧...

相关阅读

相关 PTA 6-5 最小生成树（克鲁斯卡尔算法）

kruskal算法原理在连通网中查找[最小生成树][Link 1]的常用方法有两个，分别称为[普里姆算法][Link 2]和克鲁斯卡尔算法。本节，我们给您讲解克鲁斯卡尔

缺乏、安全感/ 2024年02月05日 11:04/ 0 赞/ 50 阅读

相关【数据结构】最小生成树之克鲁斯卡尔算法

基本概念假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑如何在最省经费的前提下完成任务。在一个连通网的所有生成树中，各边的代价

我就是我/ 2022年10月02日 12:52/ 0 赞/ 201 阅读

相关 C++ 最小生成树之kruskal（克鲁斯卡尔）算法

最小生成树之kruskal（克鲁斯卡尔）算法 kruskal算法：同样解决最小生成树的问题，和prim算法不同，kruskal算法采用了边贪心的策略，思想要比pri

ゝ一纸荒年。/ 2022年06月12日 04:54/ 0 赞/ 325 阅读

相关最小生成树--克鲁斯卡尔算法

算法描述：假设连通网N=（V,\{ E \}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，\{ \}），图中每一个顶点自成

秒速五厘米/ 2022年06月11日 07:13/ 0 赞/ 237 阅读

相关最小生成树-kruskal算法（克鲁斯卡尔算法）

克鲁斯卡尔解决最小生成树的问题，克鲁斯卡尔算法的思想是将所有边按照权值，从小到大排列起来，然后依次从小到大选择边，如果选择的边会造成回路，那么放弃选择一个更大的边。 ![Ce

左手的ㄟ右手/ 2022年06月10日 12:49/ 0 赞/ 226 阅读

相关 POJ 1861 Network（最小生成树+克鲁斯卡尔）

Andrew is working as system administrator and is planning to establish a new network in

快来打我*/ 2022年06月10日 11:36/ 0 赞/ 188 阅读

相关最小生成树-Kruskal(克鲁斯卡尔)算法

最小生成树-Kruskal(克鲁斯卡尔)算法 -------------------- 简述生成树：生成树：给定一个无向图(顶点间连线不带方

﹏ヽ暗。殇╰゛Y/ 2022年05月15日 06:42/ 0 赞/ 283 阅读

相关最小生成树------克鲁斯卡尔算法（数据结构）

树（Tree）：如果一个无向连通图中不存在回路，则这种图称为树。生成树（Spanning Tree）：无向连通图G的一个子图如果是一颗包含G的所有顶点的树，则该子图

超、凢脫俗/ 2022年04月18日 01:55/ 0 赞/ 252 阅读

相关 [模板] Kruskal算法 && 克鲁斯卡尔重构树

克鲁斯卡尔重构树发现没把板子放上来... 现在放一下克鲁斯卡尔算法的正确性是反证法保证的. 大概来说, 就是如果不加入当前权值最小的边 \\(e\_1\\), 那么

ゞ浴缸里的玫瑰/ 2022年01月08日 00:41/ 0 赞/ 334 阅读

相关最小生成树-克鲁斯卡尔模板

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int fat[...

红太狼/ 2021年03月25日 14:46/ 0 赞/ 537 阅读