2024/2/20

P3366 【模板】最小生成树

题目描述

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

输入格式

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

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

输出格式

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

最小生成树

定义

图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

也就是一个有n个点的图，从中选n-1条边，使n个点相连通，并且权值最小

可以用kruskal算法和prim算法求出。

kruskal算法

是通过将每条边的权值进行排序，并通过排序的大小来选择合适的边

如果G=(V，E)是一个具有n个顶点e条边的带权连通无向图,

构造一个拥有n个顶点，而且边集为空的子图，

每次选取一条权值最小的边进行连接，如果没有形成环（即这条边的两个订点属于两个不同的树），则取这条边，否则则取下一条权值最小的边，直到所有节点连接成一条树为止（即含有n-1条边为止）

具体方法

1. 将边按权值排序
2. 初始化并查集，将每个节点的父节点都初始化为自己
3. 遍历并合并，如果两个点不在同一个集合里则，将其合并，否则跳过
4. 如果合并的边达到n-1则代表连通了

排序

bool cmp(edge a,edge b)
{
	return a.val<b.val;//快排
}

合并部分

int find(int x)
{
	if(fa[x]==x)
	{
		return x;
	}
	else
	{
		return fa[x]=find(fa[x]);
	}
}
int kruskal()
{
	for(int i=1;i<=m;i++)
	{
		u=find(bian[i].start);
		v=find(bian[i].to);
		if(u==v)
		{
			continue;
		}
			ans+=bian[i].val;
			fa[u]=v;
			sum++;	
	}
	return sum;
}

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,u,v,sum;
struct edge{
	int start,to;
	long long val;
}bian[2000005];
int fa[100000];
long long ans;
int find(int x)
{
	if(fa[x]==x)
	{
		return x;
	}
	else
	{
		return fa[x]=find(fa[x]);
	}
}
bool cmp(edge a,edge b)
{
	return a.val<b.val;
}
int kruskal()
{
	for(int i=1;i<=m;i++)
	{
		u=find(bian[i].start);
		v=find(bian[i].to);
		if(u==v)
		{
			continue;
		}
			ans+=bian[i].val;
			fa[u]=v;
			sum++;	
	}
	return sum;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>bian[i].start>>bian[i].to>>bian[i].val;
	}
	sort(bian+1,bian+m+1,cmp);
	kruskal();
	if(sum==n-1)
	cout<<ans;
	else
	cout<<"orz";
	return 0;
}