poj 3625 Building Roads （最小生成樹）

坐標類型的最小生成樹

注意，所有的距離用double，所有的int用__int64

[csharp] 
#include"stdio.h" 
#include"math.h" 
#include"string.h" 
#define INF 100000000 
double map[1001][1001],f[1001]; 
int mark[1001],n; 
void prime() 
{ 
    __int64 i,j,k; 
    double min,ans; 
    memset(mark,0,sizeof(mark)); 
    for(i=1;i<=n;i++) 
        f[i]=map[1][i]; 
    f[1]=0; 
    mark[1]=1; 
    ans=0; 
    for(i=1;i<n;i++) 
    { 
        min=INF; 
        for(j=1;j<=n;j++) 
        { 
            if(!mark[j]&&f[j]<min) 
            { 
                min=f[j];k=j; 
            } 
        } 
        ans+=min; 
        mark[k]=1; 
        for(j=1;j<=n;j++) 
        { 
            if(!mark[j]&&map[k][j]<f[j]) 
                f[j]=map[k][j]; 
        } 
    } 
    printf("%.2f\n",ans); 
} 
int main() 
{ 
    __int64 m,i,j,x[1001],y[1001],a,b; 
    while(scanf("%I64d%I64d",&n,&m)!=-1) 
    { 
        memset(map,76,sizeof(map)); 
        for(i=1;i<=n;i++) 
            scanf("%I64d%I64d",&x[i],&y[i]); 
        for(i=1;i<=n;i++) 
        { 
            for(j=i+1;j<=n;j++) 
                map[j][i]=map[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); 
        } 
        for(i=0;i<m;i++) 
        { 
            scanf("%I64d%I64d",&a,&b); 
            map[a][b]=map[b][a]=0; 
        } 
         
        prime(); 
    } 
    return 0; 
}