Poj(2560),最小生成树，Prim

题目链接：http://poj.org/problem?id=2560

只想说“全都是套路”，关键建图。

#include <stdio.h>

#include <string.h>

#include <math.h>

#define INF 0x3f3f3f3f

int n;

double maps[][];

bool vis[];

double dis[];

struct Point {

    double x;

    double y;

}points[];

double Prim()

{

    memset(vis,false,sizeof(vis));

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

        dis[i] = INF;

    dis[] = ;

    double ans =;

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

    {

        double tmp = INF;

        int k =;

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

        {

            if(!vis[j]&&dis[j]<tmp)

            {

                tmp = dis[j];

                k= j;

            }

        }

        vis[k]=true;

        ans+=tmp;

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

        {

            if(!vis[i]&&dis[i]>maps[k][i])

                dis[i] = maps[k][i];

        }

    }

    return ans;

}

int main()

{

    scanf("%d",&n);

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

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

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

    {

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

        {

            double x = points[i].x - points[j].x;

            double y = points[i].y - points[j].y;

            maps[i][j] = sqrt(x*x+y*y);

        }

    }

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

    return ;

}