poj3625 解题报告

又是一道最小生成树,拿来测模板;

题意:N个点,坐标给出,然后有M条路已经修好了,给出这M条路的起始点和终点,求需要再修多远的路才能得到最小生成树

题解:把已经修好的路长度算0,然后最小生成树就好了;话说我wa了一次,题目说了全部用64位的运算,我没看到,把坐标改成longlong就过了

好水啊;

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std ;

const int MAXN = 1005 ;

struct  Edge
{
    int  start , end ;
    double length ;
} edge[MAXN * MAXN] ;

struct  Point
{
    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 ;
}