最小生成树

#include<bits/stdc++.h> using namespace std; const int INF = 1e9; const int VM = 103; int G[VM][VM]; void prim(int n){ int dis[VM]; bool visit[VM]; int i,ans=0; memset(visit,0,sizeof(visit)); for( i=1;i<=n;i++) dis[i]=G[1][i]; dis[1]=0; visit[1]=1; for( i=2;i<=n;i++){ int u=INF; int k; for(int j=1;j<=n;j++){ if(!visit[j]&&dis[j]<u){ k=j; u=dis[j]; } } if(u==INF) break; visit[k]=1; ans+=u; for(int j=1;j<=n;j++){ if(!visit[j]&&dis[j]>G[k][j]) dis[j]=G[k][j]; } } if(i==n+1) cout<<ans<<endl; else cout<<"非联通图"<<endl; } int main(){ int n,m; while(cin>>n>>m&&n){ for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ G[i][j]=i==j?0:INF; } } while(n--){ int u,v,w; cin>>u>>v>>w; if(G[u][v]>w) G[u][v]=G[v][u]=w; } prim(m); } return 0; }