求最小生成树最基本的两种算法,当然,还有其他算法。
Prim
和dijkstra类似,采用红白点思想,就是选中一个起始点,标为红点,其他为白点,然后开始循环,找离所有被标记的红点最近的那个点,并将其标为红点,接着用这个点更新剩余的白点到所有的红点的最短距离,
如此循环n次,得到答案。
#include<bits/stdc++.h> using namespace std; int f[100][100],mt,ft[100],dis[100],n,m; void input() { int u,v,w; cin>>n>>m; memset(f,0x7f,sizeof(f)); memset(ft,0,sizeof(ft)); memset(dis,0x7f,sizeof(dis)); ft[1]=true; dis[1]=0; for(int i=1;i<=m;i++) { cin>>u>>v>>w; f[i][i]=0; f[u][v]=f[v][u]=w; } for(int i=1;i<=n;i++) dis[i]=min(dis[i],f[1][i]); } void prim() { int k,minn; for(int i=1;i<=n;i++) { k=0;minn=1e9; for(int i=1;i<=n;i++) { if(!ft[i]&&dis[i]<minn) { k=i; minn=dis[i]; } } ft[k]=true; if(k==0) break; mt=mt+dis[k]; for(int i=1;i<=n;i++) if(!ft[i]) dis[i]=min(dis[i],f[i][k]); } } void output() { cout<<mt; } void text1() { input(); prim(); output(); } int main() { text1(); return 0; }
Kruscal
这个思路很简单,从最小的边开始从小到大枚举,若此边所连的两点至少一点还没有被标记,那么,将此边加入最小生成树并标记点。
#include<bits/stdc++.h> using namespace std; int father[100],n,m,k,mt; struct ed { int from; int to; int w; }edge[100]; bool cmp(ed a,ed b) { if(a.w!=b.w) return a.w<b.w; } int fat(int x) { if(father[x]!=x) father[x]=fat(father[x]); return father[x]; } void unionn(int a,int b) { int fa,fb; fa=fat(a); fb=fat(b); if(fa!=fb) father[fa]=fb; } void input() { cin>>n>>m; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=m;i++) cin>>edge[i].from>>edge[i].to>>edge[i].w; sort(edge+1,edge+m+1,cmp); } void kruscal() { for(int i=1;i<=m;i++) { if(fat(edge[i].from)!=fat(edge[i].to)) { k++; mt+=edge[i].w; unionn(edge[i].from,edge[i].to); } if(k==n-1) break; } } void output() { cout<<mt; } void text1() { input(); kruscal(); output(); } int main() { text1(); return 0; }
后记:nothing