图结构练习——最小生成树(kruskal算法（克鲁斯卡尔）)-白红宇的个人博客

图结构练习——最小生成树(kruskal算法（克鲁斯卡尔）)

发布日期：2021-05-09 04:13:46 浏览次数：15 分类：博客文章

本文共 1001 字，大约阅读时间需要 3 分钟。

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

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。

输入

输入包含多组数据，格式如下。

第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n<=100)

剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。

输出

每组输出占一行，仅输出最小花费。

示例输入

3 21 2 11 3 11 0

示例输出

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 struct vode 5 { 6     int u,v,w; 7 }edge[70000]; 8 int m,n; 9 int f[70000];10 int cmp(const void *a,const void *b)//注意此函数的使用方法和定义方法11 {12     struct vode *c=(struct vode *)a;13     struct vode *d=(struct vode *)b;14     return c->w-d->w;15 }16 int find(int v)17 {18     int t=v;19     while(f[t]!=0)//此语句目的是寻找节点v的根节点20     t=f[t];21     return t;22 }23 int krusal()24 {25     memset(f,0,sizeof(f));26     int i,root1,root2;27     int sum=0;28     for(i=0;i

View Code

本题还有不明之处：题目限定节点的数目在0~100之间，那么，边的数目就在0~100*99/2=4950之间，为什么我数组开到了5000，甚至7000都不行，开到了8000的时候提交才过，路过的大神若是明白就给我讲解一下吧，小弟不胜感激~

上一篇：图结构练习——最短路径(dijkstra算法（迪杰斯拉特）)

下一篇：图结构练习——最小生成树（prim算法(普里姆)）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！