最小生成树是什么

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

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

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()
{IOSint 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;
}