http://acm.hdu.edu.cn/showproblem.php?pid=1233
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 500 5 using namespace std; 6 const int inf=1<<30; 7 8 int g[maxn][maxn]; 9 int n,a,b,c; 10 int dis[maxn]; 11 bool vis[maxn]; 12 int sum; 13 14 void prim() 15 { 16 memset(vis,false,sizeof(vis)); 17 for(int i=1; i<=n; i++) dis[i]=g[1][i]; 18 dis[1]=0; 19 vis[1]=true; 20 for(int i=1; i<n; i++) 21 { 22 int m=inf,x; 23 for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y]; 24 vis[x]=true; 25 sum+=m; 26 for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]>g[x][y]) dis[y]=g[x][y]; 27 } 28 } 29 30 int main() 31 { 32 while(scanf("%d",&n)!=EOF) 33 { 34 if(n==0) break; 35 for(int i=0; i<n*(n-1)/2; i++) 36 { 37 scanf("%d%d%d",&a,&b,&c); 38 g[a][b]=g[b][a]=c; 39 } 40 sum=0; 41 prim(); 42 printf("%d ",sum); 43 } 44 return 0; 45 }