小哈哈

用户名：20180390139

访问量：19724

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6366
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了
浏览：397

蓝桥杯2015年第六届真题-赢球票-题解(C++代码)-------------队列的出队入队，很简单的
浏览：342

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

数据结构-最小生成树-题解(C语言代码)-----------并查集Kruskal算法

　　作者: 小哈哈　　　　发表时间：2019-11-15 22:08:39 浏览：733　|　评论：0　

原题链接：数据结构-最小生成树

这里的程序不是Prime算法，而是Kruskal算法
对于解这个最小生成树，  其实关键的地方是先将这些边都排序一遍，从小到大
然后就开始选，从长度小的边开始选，看看这条边能不能把两个点连接在一起，都是要注意这两条边参与连接之后要保证形成的树不能  有环，也就是不能有回路嘛
  
  
    然而要判断两条边是否连通可以用DFS，BFS和并查集来判断。这里用“并查集”这个知识点，咱们可以上网搜搜，因为写下来很长，只要你会并查集 “那这道题就很简单了”
  
  关键的地方很少代码的
	#include<stdio.h>
	#define N 100
	struct edge{
	int u;   //表示u这条边和v这条边的长度为w
	int v;
	int w;
	};

struct edge e[N];   //用来存储两条边之间的关系
	int f[N]={0},n,m;  //f[i]=j表示i的祖宗是j
	void Init(int n){
	int i;
	for(i=1;i<=n;i++){
		f[i]=i;     //开始让每一个人的祖宗都是他自己
	}
	}

int getf(int v){

if(f[v]==v)
		return v;
	else{

f[v]=getf(f[v]);
		return f[v];
	}
	}

int merge(int u,int v){

int t1,t2;
	t1=getf(u);
	t2=getf(v);

if(t1!=t2){
		f[t2]=t1;
		return 1;
	}
	return 0;
	}

void quicksort(int left,int right){

if(left>right)
		return ;

int i,j,temp;
	struct edge t;
	i=left;
	j=right;
	temp=e[left].w;

while(i!=j){

while(i<j&&e[j].w>=temp){
			j--;
		};

while(i<j&&e[i].w<=temp){
			i++;
		};

if(i<j){
			t=e[i];
			e[i]=e[j];
			e[j]=t;
		}

};

t=e[left];
	e[left]=e[i];
	e[i]=t;

quicksort(left,i-1);
	quicksort(i+1,right);
	return ;
	}

int main(){

int i,j,count,sum,k;
	int x;
	count=0,sum=0;
	scanf("%d",&n);

k=1;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			scanf("%d",&x);
			if(x!=0){
			 e[k].u=i;
			 e[k].v=j;
			 e[k].w=x;
			 k++;
			}
			
		}
	}
	m=k-1;

Init(n);
	quicksort(1,m);  //这不过是一个快速排序算法
     //这里是关键了
	for(i=1;i<=m;i++){

if(merge(e[i].u,e[i].v)){  //我要看看u这条边和v这条边有没有关系，也就是有没有在一个集合里，如果没有就可以让他们连通
			count++;  //记录连通的边
			sum+=e[i].w;
		}

if(count==n-1)  //如果边连通了n-1条，那就完事了
			break;
	}

printf("%d\n",sum);
	return 0;
}

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小哈哈

TA的其他文章

你可能喜欢

交换Easy （C++代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

数据结构-最小生成树-题解(C语言代码)-----------并查集Kruskal算法

评论区

精彩推荐

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

【绝对值排序】（C语言代码）

最小公倍数（C语言代码）

整除的尾数（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

小哈哈

TA的其他文章

你可能喜欢

交换Easy （C++代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

数据结构-最小生成树-题解(C语言代码)-----------并查集Kruskal算法

评论区

精彩推荐

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

【绝对值排序】 （C语言代码）

最小公倍数 （C语言代码）

整除的尾数 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

Tom数（C语言代码）

　　评论区

【绝对值排序】（C语言代码）

最小公倍数（C语言代码）

整除的尾数（C语言代码）