prim模板

int g[N][N],dist[N],n,m,ans; int st[N]; void prim() {memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++) if(!st[j]&&(t==-1 || dist[j]<dist[t])) t=j;if(dist[t]==0x3f3f3f3f) return;st[t]=1;ans+=dist[t];for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);} }

kruskal模板

const int N=1e5+10; int p[N],n,m,sum,cnt; struct node{int a,b,c;}; int find(int x) {if(x!=p[x]) p[x]=find(p[x]);return p[x]; } bool cmp(node a,node b){return a.c<b.c;} vector<node>ve; void kruskal() {for(int i=1;i<=n;i++) p[i]=i;sort(ve.begin(),ve.end(),cmp);for(int i=0;i<ve.size();i++){int a=ve[i].a,b=ve[i].b,c=ve[i].c;if(find(a)==find(b)) continue;sum+=c,cnt++;p[find(a)]=find(b);} }

858. Prim算法求最小生成樹
859. Kruskal算法求最小生成樹

總結

以上是生活随笔為你收集整理的ACM入门之【最小生成树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。