#include <iostream>
#include <stdio.h>
using namespace std; 
 
const int N=102 ;
bool flag[N] ;
int dis[N][N] ; 
const int MAX = 0x7fffffff; 
int MST_Prim( const int n ) // n is the size of the graph  
{
     int i , m=1 ,  j , k  ; 
     for( i=0 ; i<n ; i++ )
        if( flag[i] == true ) m ++ ; 
     if( m == 1 ){ flag[1] = true ; m ++ ;} 
     
     int min , lable ; 
     int distance = 0 ; 
     for (k=0; k<=n-m; k++)
     {
         min=MAX;
         for(i=0; i<n; i++)
         {
             if (flag[i])
             for (j=0; j<n; j++)
             if ( !flag[j] && i!=j )
             {
                  if (dis[i][j]<min)
                  {
                      min=dis[i][j];
                      lable=j;
                  }
             }
         }
         distance += min;
         flag[lable]=true;
     } 
     return distance ;          
}



int main()
{
	int a , b , m ,n ; 
	int distance = 0 ; 
	scanf( "%d" , &n ) ;
	for( int i=0 ; i<n ; i++ )
	    for( int j=0 ; j<n ;j++ )
	       scanf( "%d" , &dis[i][j] ) ; //输入图 
	       
	scanf( "%d" ,&m ) ; 
	for( int i=0 ; i<m ; i++ )
	{
		scanf( "%d%d"  , &a , &b ) ; 
		flag[a-1] = true , flag[b-1] = true ;  
	}//输入已经联上的村庄 
	distance = MST_Prim( n ) ; 
	printf( "%d\n"  , distance ) ; 
    cin >> distance ;
	return 0 ; 
}

• mmmm.... (0) Trident 2006-01-24 14:43:56
• Re:分组有错 (124) gaojinjun 2006-07-03 10:50:13