题目描述

给出N个点的坐标，对它们建立一个最小生成树，代价就是连接它们的路径的长度，现要求总长度最小。N的值在100以内，坐标值在[-10000,10000].结果保留二位小数

输入

5 —————5个点
0 0 —————5个点点的坐标
0 1
1 1
1 0
0.5 0.5

输出

2.83

思路

把每一个点的坐标先记录下来，然后算出每一个点之间的距离，然后用PRIM求解

#include 
#include 
using namespace std;
double a[101][101];
double b[101][3];
int f[101];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lf%lf",&b[i][1],&b[i][2]);

    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            a[i][j]=sqrt(((b[i][1]-b[j][1])*(b[i][1]-b[j][1]))+((b[i][2]-b[j][2])*(b[i][2]-b[j][2])));
    }
    double ans=0.0;
    f[1]=1;
    for (int k=1;k<=n-1;k++)
    {
        double min=100000000;
        int t=0;
        for (int i=1;i<=n;i++)
            if (f[i]==1)
            {
                for (int j=1;j<=n;j++)
                    if (f[j]==0&&a[i][j]