1825: 【模板】最小生成树

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

参考文档：https://blog.csdn.net/ZhuRanCheng/article/details/119791246

【prime算法】

#include<iostream>
#include<algorithm> 
using namespace std;

const int N = 5005;
const int M = 200005;

int n,m;

//并查集
int pre[N];
int find(int x){
	int r = x;
	while(pre[r]!=r){
		r = pre[r];
	}
	
	int k = x;
	while( pre[k]!=r ){
		k = pre[k];
		pre[k] = r;
	}
	return r;
} 

void join(int x,int y){
	int fx = find(x),fy = find(y);
	if( fx != fy ) pre[fx] = fy;
}

//邻接表存图
struct edge{
	int x,y,z;
}e[2*M];

bool cmp(edge a, edge b){
	return a.z < b.z ;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) pre[i] = i;
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		e[i] = (edge){x,y,z};
	}
	sort(e+1,e+m+1,cmp); 
	
	int cnt = 0;
	int sum = 0;
	for(int i=1;i<=m;i++){
		if( find(e[i].x) != find(e[i].y) ){
			cnt++;
			join(e[i].x,e[i].y);
			sum += e[i].z;
		}
	}
	if( cnt == n-1 ) cout<<sum;
	else cout<<"orz";
	
	return 0;
}

【kruskal算法】

#include<bits/stdc++.h>
using namespace std;
const int N =5005;
const int M = 200005;
const int oo = 0x3fffffff;

struct node{
	int to,w;
	bool operator > (const node &x)const{
		return w>x.w;
	}
}; 
//struct cmp{
//	bool operator () (const node &a, const node &b) {
//		return a.w > b.w ;
//	}		
//};

vector<node> G[N];
int d[N];
int vis[N];



int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) d[i] = oo;
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back( (node){y,z} );
		G[y].push_back( (node){x,z} );
	}
	d[1] = 0;
	
	priority_queue< node , vector<node> ,greater<node> > q; 
	q.push( (node){ 1,0 } );
	while(!q.empty()){
		int k = q.top().to;
		q.pop();
		if( vis[k] == 1 ) continue;
		vis[k] = 1;
		for(int j=0;j<G[k].size();j++){
			int to = G[k][j].to;
			int w = G[k][j].w;
			if( w < d[to] && !vis[to] ){
				d[to] = w;
				q.push( (node){to,w} ); 
			}
		}		
	}

	bool flag = 1;
	int sum = 0;
	for(int i=1;i<=n;i++){
		if( vis[i] == 0 ){
			flag = 0;
			break;
		}	
		sum += d[i];
	}
	if( flag ) cout<<sum;
	else cout<<"orz";
	return 0;
}

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

接下来 M 行每行包含三个整数 Xi,Yi,Zi，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。

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

7