「剑鱼行动」剑鱼行动

剑鱼行动

题目大意：

Description

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

Input

5 —————5个点

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

0 1

1 1

1 0

0.5 0.5

Output

2.83

解题思路：

勾股预处理后最小生成树

源程序：

#include <cstdio>
#include <cmath>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,p;
double ans,mins,a[101][101],v[101],x[101],y[101],w,s;
bool d[101];
int main()
{
    scanf("%d",&n);
    r(i,1,n) scanf("%lf%lf",&x[i],&y[i]);
    r(i,1,n)
     r(j,1,n)
      if(i==j) v[i]=0,a[i][j]=0;
       else 
       {
        w=(abs(x[j]-x[i]))*(abs(x[j]-x[i]));
        s=(abs(y[j]-y[i]))*(abs(y[j]-y[i]));
        a[j][i]=a[i][j]=sqrt(w+s);
       }
    r(i,1,n) v[i]=a[1][i];
    r(k,1,n-1)
    {
        mins=1000000;
        r(i,1,n)
          if (v[i]<mins&&v[i])
           {mins=v[i];p=i;}
        ans+=mins;      
        v[p]=0;
        r(i,1,n)
         if(a[p][i]<v[i])
          v[i]=a[p][i];
    }
    printf("%0.2lf",ans);
}