最小生成树Prim算法

最小生成树是什么

最小生成树是使图中连接起来与小的最小代价

上边这张图的最小生成树就是下图

Prim算法是什么

Prim算法就是给你一个起点，每次找与这个点相邻边的最小值，直到遍历每个节点

模板

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define int long long
#define endl '\n'
#define PII pair<int,int> 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n,m,st[100],d[100];
struct asd{
	int v,w;
};
vector<asd>v[100];
void init()
{
	for(int i=0;i<=n;i++)
	{
		st[i]=0;
		v[i].clear();
		d[i]=1e9;
	}
}
int prim()
{
	d[1]=0;
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		int u=0;
		for(int j=1;j<=n;j++)
		{
			if(d[u]>d[j]&&!st[j])
			u=j;
		}
		sum+=d[u];
	    st[u]=1;
	    for(auto x:v[u])
	    {
	    	if(d[x.v]>x.w)
	    	d[x.v]=x.w;
		}
	}
	return sum;
 } 
signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		int a,b,c;
		while(cin>>n&&n)
		{
			init();
			cin>>m;
			while(m--)
			{
				cin>>a>>b>>c;
				v[a].push_back({b,c});
				v[b].push_back({a,c});
			} 
			cout<<prim()<<endl;
		}
	}
	return 0;
}