kurskal算法的模板应用

洛谷P3366
题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式

第一行包含两个整数 N,MN,MN,M，表示该图共有 NNN 个结点和 MMM 条无向边。

接下来 MMM 行每行包含三个整数 Xi,Yi,ZiX_i,Y_i,Z_iXi​,Yi​,Zi​，表示有一条长度为 ZiZ_iZi​ 的无向边连接结点 Xi,YiX_i,Y_iXi​,Yi​。
输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

7

说明/提示

数据规模：
最后达到n<=5e3;m<=2e5;z<=1e4

好久没更新了，kurskal算法本质是加边，因为是最小生成树，所以每次加边加剩余边边权最小的，通过并查集，防止出现已经联通的区域形成环，边具有两点和边权这3个属性，利用结构体

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
//kurskal算法下的最小生成树 
typedef long long ll;
int n,m;
int flag=0;
const int maxn =5e3+5;
const int inf=0x3f3f3f3f;
const int maxm=2e5+5;
int fat[maxn];
struct node{//边的状态 
	int from;
	int to;
	int w;
}nodes[maxm];
bool cmp(const node &a,const node &b){
	return a.w<b.w;//和优先队列有些不一样，这里小的先进，小的先出,升序 
}
void bcinit(){//并查集的基础操作 
	for(int i=1;i<=n;i++){ 
		fat[i]=i; //
	}
}
int findfa(int u){
	if(fat[u]==u){
		return u;
	}
	return fat[u]=findfa(fat[u]);
}
void beunion(int u,int v){//注意合并方式 
	fat[findfa(v)]=findfa(u);
}
ll kurskal(){
	int cnt=0;
	ll ans=0;
	sort(nodes+1,nodes+1+m,cmp);
	for(int i=1;i<=m;i++){//加边 
		if(cnt==n-1){
			break;
		}
		if(findfa(nodes[i].from)!=findfa(nodes[i].to)){
			ans+=nodes[i].w;
			beunion(nodes[i].from,nodes[i].to);
			cnt++;
		}
	}
	for(int i=1;i<n;i++){
		if(findfa(i)!=findfa(i+1)){
			flag=1;
			break;
		}
	}
	return ans;
} 
int main(){
	int u,v,wa;
	scanf("%d%d",&n,&m);
	bcinit();
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&wa);
		nodes[i].from=u;
		nodes[i].to=v;
		nodes[i].w=wa;
	}
	ll ans=kurskal();
	if(flag==1)
		printf("orzn");
	else{
		printf("%lldn",ans);
	}
	return 0;
}

看下以后能不能日日更新

最后

以上就是自由黑米为你收集整理的kurskal算法的模板应用的全部内容，希望文章能够帮你解决kurskal算法的模板应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。