还是prim
预处理那些已经修好的路，变为0,即可。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 const int maxn = 103; 4 const int inf = 9999999; 5 struct node{ 6 int cost,is; 7 }mat[ maxn ][ maxn ]; 8 int dis[ maxn ],vis[ maxn ]; 9 int n,sum; 10 11 int prim(){ 12 memset( vis,0,sizeof(vis)); 13 for( int i=1;i<=n;i++ ) 14 dis[ i ]=mat[ 1 ][ i ].cost; 15 vis[ 1 ]=1; 16 for( int i=1;i<=n;i++ ){ 17 int t,max; 18 t=-1,max=inf; 19 for( int j=1;j<=n;j++ ){ 20 if( vis[ j ]==0 && max>dis[ j ]){ 21 t=j,max=dis[ j ]; 22 } 23 } 24 if( t==-1 ) return sum; 25 sum+=max; 26 vis[ t ]=1; 27 for( int j=1;j<=n;j++ ){ 28 if( vis[ j ]==0 && dis[ j ]>mat[ t ][ j ].cost){ 29 dis[ j ]=mat[ t ][ j ].cost; 30 } 31 } 32 } 33 return sum; 34 } 35 36 int main(){ 37 while( scanf("%d",&n)!=EOF,n ){ 38 int nn=n*(n-1)/2; 39 int a,b,c,d; 40 sum=0; 41 memset( vis,0,sizeof( vis )); 42 while( nn-- ){ 43 scanf("%d%d%d%d",&a,&b,&c,&d); 44 mat[ a ][ b ].cost=mat[ b ][ a ].cost=c; 45 mat[ a ][ b ].is=mat[ b ][ a ].is=d; 46 if( d==1 ){ 47 //sum+=c; 48 mat[ a ][ b ].cost=mat[ b ][ a ].cost=0; 49 } 50 } 51 int ans=prim(); 52 printf("%d\n",ans); 53 } 54 return 0; 55 }