雖然這一題已經(jīng)寫過了，但是我覺得這里有問題。因為題目中有這樣的一句話：
We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
這樣一來，如果是A-B-C-D，我們能說A和D是相通的嗎？我覺得不能，但是參考別人的代碼時，他們都沒有考慮這一中情況，我也寫了一個沒有考慮的。竟然過了！不知道為什么。我主要是在練習(xí)算法，難道是我理解錯了？
#include <stdio.h>
#define DEBUG 1
const int Max = 0x7fffffff ;
const int N = 111 ;
int n, dis[N], used[N], closest[N], map[N][N] ;
int Prim( )
{
int i, j, index, min, len ;
for( i=1; i<=n; ++i ){
used[i] = 0 ;
dis[i] = map[1][i] ;
}
used[1] = 1 ;
len = 0 ;
for( i=1; i<n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
len += dis[index] ;
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[j][index] )
dis[j] = map[j][index] ;
}
}
return len ;
}
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
#endif
int i, j, x, y, comp ;
while( EOF != scanf("%d", &n ) && n ){
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
scanf("%d", &map[i][j] ) ;
map[j][i] = map[i][j] ;
}
}
scanf("%d", &comp ) ;
for( i=1; i<=comp; ++i ){
scanf("%d%d", &x, &y ) ;
map[x][y] = map[y][x] = 0 ;
}
printf("%d\n", Prim( ) ) ;
}
return 0 ;
}