例如;如下图,构造一棵最小生成树
构造过程:
#include<iostream> #include<algorithm> #include<cstring> #include<iomanip> #include<cmath> using namespace std; const int maxx=505; const int inf=0x3f3f3f3f; int e[maxx][maxx];//记录两点之间的权值 int n,m; int vis[maxx];//记录访问情况 int dist[maxx];//记录最短距离 int p[maxx];//记录前驱节点 int mincost;//记录最小费用 void Prim(int u){ for(int i=1;i<=n;i++){ dist[i]=e[u][i]; p[i]=u; } vis[u]=1; dist[u]=0; for(int i=1;i<=n;i++){ double temp=inf; int t=u; for(int j=1;j<=n;j++){ if(!vis[j]&&dist[j]<temp){ temp=dist[j]; t=j; } } if(t==u)break; vis[t]=1; mincost+=dist[t]; for(int j=1;j<=n;j++){ if(!vis[j]&&dist[j]>e[t][j]){ dist[j]=e[t][j]; p[j]=t; } } } } int main(){ int t; while(cin>>n>>m){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j){ e[i][j]=0; }else{ e[i][j]=inf; } } } memset(vis,0,sizeof(vis)); memset(p,0,sizeof(p)); memset(dist,inf,sizeof(dist)); for(int i=1;i<=m;i++){ int a,b,cost; scanf("%d %d %d",&a,&b,&cost); e[a][b]=e[b][a]=cost; } mincost=0; Prim(1); cout<<"最小费用: "<<mincost<<endl; } return 0; } /* 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 5 6 5 6 6 3 6 4 3 4 5 4 6 2 */