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[300][300];
bool vis[300];
double dis[300];

struct Point {
    double x;
    double y;
}points[300];

double Prim()
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i] = INF;

    dis[1] = 0;
    double ans =0;
    for(int i=1;i<=n;i++)
    {
        double tmp = INF;
        int k =0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<tmp)
            {
                tmp = dis[j];
                k= j;
            }
        }

        vis[k]=true;
        ans+=tmp;
        for(int i=1;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=1;i<=n;i++)
        scanf("%lf%lf",&points[i].x,&points[i].y);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;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
",Prim());

    return 0;
}