poj3625 解題報告

又是一道最小生成樹,拿來測模板;

題意:N個點,坐標給出,然後有M條路已經修好了,給出這M條路的起始點和終點,求需要再修多遠的路才能得到最小生成

樹

題解:把已經修好的路長度算0,然後最小生成樹就好了;話說我wa了一次,題目說了全部用64位的運算,我沒看到,把坐標

改成longlong就過了

好水啊;

[cpp] 
#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 ; 
}