设为首页 加入收藏

TOP

poj3625 解题报告(二)
2012-12-17 13:02:19 来源: 作者: 【 】 浏览:559
Tags:poj3625  解题 报告

 

    {

    long long  x , y ;

    } point[MAXN] ;

    int  father[MAXN] , Count ;

    bool vis[MAXN][MAXN] ;

    double  getlength( Point a , Point b )

    {

    double len ;

    len = sqrt( double ( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) ) ) ;

    return len ;

    }

    bool  cmp( Edge a , Edge b )

    {

    return a.length < b.length ;

    }

    int  find( int x )

    {

    if( father[x] == x ) return x ;

    father[x] = find( father[x] ) ;

    return father[x]              ;

    }

    bool Union( int x , int y )

    {

    int  f1 = find( x ) ;

    int  f2 = find( y ) ;

    if( f1 == f2 ) return false ;

    else if( f1 < f2 ) father[f1] = f2 ;

    else father[f2] = f1 ;

    return true ;

    }

    double kruskal( int n )

    {

    int  i , j = 0 ;

    double sum = 0 ;

    for( i = 0 ; i < n ; i ++ )

    father[i] = i ;

    sort( edge , edge + Count , cmp ) ;

    for( i = 0 ; i < Count && j < n ; i ++ )

    {

    if( Union( edge[i].start , edge[i].end ) )

    {

    sum += edge[i].length  ;

    j ++ ;

    }

    }

    return sum ;

    }

    int  main()

    {

    int  M , N ;

    int  i , j , start , end ;

    Count = 0 ;

    memset( vis , 0 , sizeof ( vis ) ) ;

    scanf( “%d%d” , & N , & M ) ;

    for( i = 0 ; i < N ; i ++ )

    scanf( “%d%d” , & point[i].x , & point[i].y ) ;

    for( i = 0 ; i < M ; i ++ )

    {

    scanf( “%d%d” , & start , & end ) ;

    vis[start-1][end-1] = 1 ;

    vis[end-1][start-1] = 1 ;

    }

    Count = 0 ;

    for( i = 0 ; i < N - 1 ; i ++ )

    for( j = i + 1 ; j < N ; j ++ )

    {

    edge[Count].start = i ;

    edge[Count].end   = j ;

    if( vis[i][j] == 0 ) edge[Count].length = getlength( point[i] , point[j] ) ;

    else edge[Count].length = 0 ;

    Count ++ ;

    }

    //for( i = 0 ; i < Count ; i ++ )

    //    cout << edge[i].start << “ ” << edge[i].end << “ ” << edge[i].length << endl ;

    printf( “%.2f\n” , kruskal( N ) ) ;

    return 0 ;

    }

      

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇struct结构体内的对齐问题 下一篇计算多边形的面积

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: