没什么好说的,还是最小生成树,和上一题一样,没有任何变化。我现在只会prim算法,所以就只用prim写。
#include <stdio.h>
#define DEBUG 1
const int N=101 ;
const int Max = 0x7fffffff ;
int n, map[N][N], dis[N], used[N], closest[N] ;
int Prim( )
{
int i, j, index, min, len ;
len = 0 ;
for( i=1; i<=n; ++i ){
dis[i] = map[1][i] ;
used[i] = 0 ;
closest[i] = 1 ;
}
used[1] = 1 ;
for( i=1; i<n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
min = dis[j] ;
index = j ;
}
}
used[index] = 1 ;
len += dis[index] ;
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[index][j] ){
closest[j] = index ;
dis[j] = map[index][j] ;
}
}
}
return len ;
}
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
int i, j, x, y, weight, hangshu ;
while( scanf("%d", &n) && n ){
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
map[i][j] = Max ;
}
}
hangshu = n*(n-1)/2 ;
for( i=1; i<=hangshu; ++i ){
scanf("%d%d%d", &x, &y, &weight ) ;
map[x][y] = map[y][x] = weight ;
}
printf("%d\n", Prim( ) ) ;
}
return 0 ;
}