krusal算法求最小生成树（贪心）

⬅ 返回

1、算法思路

2、例题

3、代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define PI 3.14159
using namespace std;
 
typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e6+15;
const int mod = 1e9+7;
int n,m;
int f[N];
struct Edge{
	int u,v,w;
};
Edge edge[N];
//结构体排序采用这种方式，清晰，小的在前面；
bool cmp(Edge e1,Edge e2)
{
	return e1.w<e2.w;//从小到大排序 
}
int find_root(int x)// 并查集
{
	if(f[x]!=x)
		f[x]=find_root(f[x]);
	return f[x];
}
 
int res=0;
int node=0;
 
void krusal()
{
	sort(edge,edge+m,cmp);//结构体排序，自己写一下cmp
	for(int i=1;i<=n;i++)
		f[i]=i;
	
	//kruskal算法：从最小的边开始画，直到把整个图画通。
	for(int i=0;i<m;i++)
	{
		int u=edge[i].u;
		int v=edge[i].v;
		int w=edge[i].w;
		int fu = find_root(u);
		int fv = find_root(v);
		if(fu!=fv)
		{
			f[fu]=fv;
			res+=w;
			node++;
		}
	}
	
	
	
	
}
 
void solve()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		edge[i]={a,b,c};
	}
	krusal();
	if(node!=n-1)
		cout<<"impossible"<<endl;
	else
		cout<<res<<endl; 
}
 
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
    int T = 1;
    while(T--)
    {
        solve();
    }
}