POJ1287 Networking【最小生成树】

#include <iostream>#define maxn 55#define inf 1<<29using namespace std;int map[maxn][maxn];int n,m;void prim(){ ???int d[maxn],vis[maxn]; ???int i,v,j,minn; ???for(i=1;i<=n;i++){ ???????vis[i]=0; ???????d[i]=map[1][i]; ???} ???for(i=1;i<=n;i++) ???{ ???????minn=inf; ???????for(j=1;j<=n;j++) ???????????if(!vis[j] && d[j]<minn) ???????????{ ???????????????minn=d[j]; ???????????????v=j; ???????????} ???????vis[v]=j; ???????for(j=1;j<=n;j++) ???????{ ???????????if(!vis[j] && map[v][j]<d[j]) ???????????????d[j]=map[v][j]; ???????} ???} ???for(d[0]=0,i=1;i<=n;i++) ??????d[0]+=d[i]; ???cout<<d[0]<<endl;}int main(){ ???int i,j,a,b,c; ???while(cin>>n,n) ???{ ???????cin>>m; ???????for(i=0;i<=n;i++) ???????{ ???????????for(j=0;j<=n;j++) ???????????????if(i!=j) map[i][j]=inf; ???????????????else map[i][j]=0; ???????} ???????for(i=0;i<m;i++) ???????{ ???????????cin>>a>>b>>c; ???????????if(map[a][b]>c) map[a][b]=map[b][a]=c; ???????} ???????prim(); ???} ???return 0;}

#include <iostream>#include <algorithm>using namespace std;typedef struct{ ???int s,t,w;}Edge;Edge edge[2500];int n,m,set[55];int cmp(const void * a,const void * b){ ???return (*(Edge *)a).w-(*(Edge *)b).w;}int find(int x){ ???if(x==set[x]) return x; ???int rt=find(set[x]); ???set[x]=rt; ???return set[x];}bool Union(int x,int y){ ???int fx=find(x); ???int fy=find(y); ???if(fx==fy) return 0; ???set[fx]=fy; ???return 1;}void kruskal(){ ???int i,sum=0; ???for(i=1;i<=m;i++) ???{ ???????if(Union(edge[i].s,edge[i].t)) ???????{ ???????????sum+=edge[i].w; ???????} ???} ???cout<<sum<<endl;}int main(){ ???int i; ???while(cin>>n,n) ???{ ???????for(i=1;i<=n;i++) ??????????set[i]=i; ???????cin>>m; ???????for(i=1;i<=m;i++) ???????{ ???????????cin>>edge[i].s>>edge[i].t>>edge[i].w; ???????} ???????qsort(edge+1,m,sizeof(edge[0]),cmp); ???????kruskal(); ???} ???return 0;}