xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

struct  arr{
    
int  x,y,c;
}a[
250010 ];
int  N,M;
int  len = 0 ;
int  No1,No2;
int  q[ 510 ];
int  p[ 510 ];
int  cmp( const   void *  no1, const   void *  no2){
    
return  ( * (arr * )no1).c - ( * (arr * )no2).c;
}
void  init()
{
    scanf(
" %d%d " , & N, & M);
    
for ( int  i = 1 ;i <= M; ++ i)
        scanf(
" %d%d%d " , & a[i].x, & a[i].y, & a[i].c);
    qsort(a
+ 1 ,M, sizeof (arr),cmp);
}
int  Find( int  x){
    
if (x != p[x]) p[x] = Find(p[x]);
    
return  p[x];
}
int  kruskal( int  ai){
    
for ( int  i = 1 ;i <= N; ++ i)
        p[i]
= i;
    
int  k = 0 ,x,y,ans = 0 ;
    
for ( int  i = 1 ;i <= M; ++ i)
        
if (ai != i){
            x
= Find(a[i].x);
            y
= Find(a[i].y);
            
if (x != y){
                ans
+= a[i].c;
                
if (ai == 0 )
                    q[
++ len] = i;
                k
++ ;
                
if (k == N - 1 return  ans;
                p[x]
= y;
            }
        }
    
return   0xFFFFFFF ;
}
int  main()
{
    init();
    No1
= kruskal( 0 );
    printf(
" Cost: %d\n " ,No1);
    No2
= 0xFFFFFFF ;
    
for ( int  i = 1 ;i <= len; ++ i){
        
int  Min = kruskal(q[i]);
        
if (No2 > Min)
            No2
= Min;
    }
    
if (No2 == 0xFFFFFFF )
        No2
=- 1 ;
    printf(
" Cost: %d\n " ,No2);
    
return   0 ;
}




posted on 2009-06-18 12:23 xfstart07 阅读(194) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理