#include <stdio.h>
#include <iostream>
using namespace std;
#define Maxim 10000000                              
#define n 101   
int kase;
typedef int AdjMatrix[n][n];                          
typedef struct{                                      
	int fromvex,tovex;                                
	int length;                                       
}TreeEdgeNode;
typedef TreeEdgeNode MST[n-1];                       
AdjMatrix G;                                          
MST T;                                               

void InitCandidateSet(AdjMatrix G,MST T,int r){
	int i,k=0;
	for(i=0;i<kase;i++)                               
		if(i!=r){                                     
			T[k].fromvex = r;                        
			T[k].tovex   = i;                         
			T[k++].length= G[r][i];                    
		}
}


int SelectLightEdge(MST T,int k){
	int min = Maxim,i,minpos;
	for(i=k;i<kase-1;i++)                                 
		if(T[i].length < min){
			min = T[i].length;
			minpos = i;                              
		}
		return minpos;                                     
}


void McandidateSet(AdjMatrix G,MST T,int k,int v){
	int i,d;
	for(i=k;i<kase-1;i++){                               
		d = G[v][T[i].tovex];                          
		if(d<T[i].length){
			T[i].length = d;
			T[i].fromvex= v;                          
		}
	}
}
void PrimMST(AdjMatrix G,MST T,int r){
	int k,m,v;
	TreeEdgeNode e;	
	InitCandidateSet(G,T,r);                           
    for(k=0;k<kase-1;k++){                               
        m = SelectLightEdge(T,k);                     
		e   = T[m];
		T[m]= T[k];
		T[k]= e;                                                  
        v   = T[k].tovex;                              
        McandidateSet(G,T,k+1,v);                 
    }
}
__int64 PrintMST(MST T){
	int i;
	__int64 sum=0;
	for(i=0;i<kase-1;i++){
		sum+=T[i].length;
	}
	return sum;
}
void main(){
	freopen("test.txt","r",stdin);
	int i,j;
	cin>>kase;
	for(i=0;i<kase;i++)
		for(j=0;j<kase;j++){
			cin>>G[i][j];
			if(i==j)
				G[i][j]= Maxim;
		}                                                      
	PrimMST(G,T,0);                              
	printf("%I64d\n",PrintMST(T));
}

• wa的厉害... (2464) mixter 2005-09-01 15:56:39