kruscal算法实现

港控/mmm° 2022-07-12 14:00 60阅读 0赞

达到的

#include <iostream>
    #include <algorithm>
    using namespace std;
    int trank[100];
    int n,m,U[100],V[100],W[100],R[100];
    int A[100];
    int par[100];
    void make_set(int n)
    {
    	for(int i=1;i<=n;i++)
    	{
    		par[i]=i;
    		trank[i]=0;
    	}
    }
    /*int  find(int x)
    {
    	//return set[x]==x?x:set[x]=find(set[x]);
    	if(set[x]==x) return x;
    	else {set[x]=find(set[x]);return find(set[x]);}//这里有瑕疵，每次调次函数只更新一次set【】
    }*/
    int find(int x)
    {
    	return par[x]==x?x:par[x]=find(par[x]);
    }
    void Union(int x,int y)
    {
    	x=find(x);
    	y=find(y);
    	if(trank[x]>trank[y])
    	{
    		par[y]=x;//y为头目；x为集合名
    	}
    	else if(trank[x]<trank[y])
    	{
    		par[x]=y;
    	}
    	else trank[x]++;
    }
    int cmp(int i,int j)
    {
    	if(W[i]<W[j]) return true;
    }
    void mst_kruskal()
    {
    	make_set(n);
    	for(int i=1;i<=m;i++)
    		R[i]=i;
    	sort(R,R+m,cmp);
    	for(int i=1;i<=m;i++)
    	{
    		if(find(U[R[i]])!=find(V[R[i]]))
    		{
    			A[i]=R[i];
    			Union(U[R[i]],V[R[i]]);
    		}
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 hihoCoer 1098 : 最小生成树二·Kruscal算法（并查集）

\1098 : 最小生成树二·Kruscal算法时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table>

比眉伴天荒/ 2024年02月17日 21:36/ 0 赞/ 14 阅读

相关实现LRU算法

本文参考Java 的 LinkedHashMap 集合源码数据结构：LinkedHashMap 说明：LinkedHashMap中有个参数 accessOrder ，

た入场券/ 2022年12月30日 01:26/ 0 赞/ 323 阅读

相关 HDU 1301-Jungle Roads (Kruscal 最小生成树)

Description ![4e1a455cd8286ae049ef90e7be32bbfb][] The Head Elder of the tropical

偏执的太偏执、/ 2022年09月22日 13:52/ 0 赞/ 143 阅读

相关贪心算法实现

一. 给出解决文件压缩问题的贪心算法 Algorithm -HUFFMAN 输入: n个字符的集合C=\{c1,c2,…,cn\}和它们的频度\{f(c1),

我就是我/ 2022年07月14日 09:40/ 0 赞/ 222 阅读

相关 kruscal算法实现

达到的 include <iostream> include <algorithm> using namespace std; in

港控/mmm°/ 2022年07月12日 14:00/ 0 赞/ 61 阅读

相关 AES算法实现

AES算法实现 1）AES：密码学中的高级加密标准（Advanced Encryption Standard，AES），又称Rijndael 加密法，是美国联邦政府采

客官°小女子只卖身不卖艺/ 2022年05月30日 10:39/ 0 赞/ 192 阅读

相关 hiho - 1098 最小生成树二·Kruscal算法

最小生成树二·Kruscal算法描述随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法

蔚落/ 2022年05月18日 07:06/ 0 赞/ 181 阅读

相关各种算法实现

排序算法 1，冒泡排序（稳定）———时间复杂度O(n^2) 冒泡排序是比较任何两个相邻元素，如果第一个比第二个大就交换两个的位置。那么较大的值就会一点一点移动到后面正确的

水深无声/ 2022年03月09日 10:08/ 0 赞/ 236 阅读

相关 HDU 1875 畅通工程再续（Kruscal最小生成树）

　　文章作者：ktyanny 文章来源：[ktyanny][] 转载请注明，谢谢合作。　　ktyanny：好吧，中文题目了，那么题目描述就不多说了。一看就是用最小生成树的思

秒速五厘米/ 2021年12月20日 14:09/ 0 赞/ 346 阅读

相关算法-java实现

1. 质因数分解 public static List<Integer> factorize(int n){ List<Integer> f

r囧r小猫/ 2021年12月16日 10:04/ 0 赞/ 243 阅读