poj 3625 Building Roads（最小生成树，二维坐标，基础）

//最小生成树，只是变成二维的了

#define  _CRT_SECURE_NO_WARNINGS

#include<stdlib.h>

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<math.h>

using namespace std;

#define inf 999999999

#define M 1010

double mat[M][M];

struct tt

{

    double x,y,z,r;

}d[M];

double prim(int n,int sta)

{

    int mark[M],i,j;

    double dis[M],sum=;

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

    {

        dis[i]=mat[sta][i];

        mark[i]=;

    }

    mark[sta]=;

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

    {

        double minn=inf*1.0;

        int flag=-;

        for(j=;j<n;j++)

        {

            if(mark[j]==&&dis[j]<minn)

            {

                minn=dis[j];

                flag=j;

            }

        }

        if(flag!=-)

        {

            mark[flag]=;

            sum=sum+dis[flag];

            for(j=;j<n;j++)

            {

                if(dis[j]>mat[flag][j])

                    dis[j]=mat[flag][j];

            }

        }

    }

    return sum;

}

int main()

{

    int i,j,n,m,xx,yy;

    double aa;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

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

        {

            scanf("%lf%lf",&d[i].x,&d[i].y);

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

            {

                aa=sqrt((d[i].x-d[j].x)*(d[i].x-d[j].x)+(d[i].y-d[j].y)*(d[i].y-d[j].y));

                mat[i][j]=mat[j][i]=aa;

            }

        }

        for(i=;i<m;i++)

        {

            scanf("%d%d",&xx,&yy);

            xx--;yy--;

            mat[xx][yy]=mat[yy][xx]=0.0;

        }

        printf("%.2lf\n",prim(n,));

    }

    return ;

}