剑鱼行动

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
分析
这题我们可以套模板——最小生成树
最优布线问题（最小生成树）
还有，这里有个知识点
坐标与坐标之间的距离（勾股定理）
求距离
代码实现

sqrt((abs(x[i]-x[j]))*(abs(x[i]-x[j]))+(abs(y[i]-y[j]))*(abs(y[i]-y[j])));

再用cout<<setprecision(2)<<fixed<<s;就行了
AC代码
prim

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
using namespace std;
int n,k,b[105];
double s,x[105],y[105],m[105],a[105][105];//定义
int main()
{
   
	cin>>n;
	for(int i=1;i<=n;i++)
	{
   
		cin>>x[i]>>y[i];
	    for(int j=1;j<n;j++)
		{
   
	    	a[i][j]=sqrt((abs(x[i]-x[j]))*(abs(x[i]-x[j]))+(abs(y[i]-y[j]))*(abs(y[i]-y[j])));//距离
	    	a[j][i]=a[i][j];//将距离也赋值给a[j][i]
		}
	} 
	memset(m,0x7f,sizeof(m));
	m[1]=0;  
	for(int i=1;i<=n;i++)//下面直接套模板
	{
   
		k=0;
		for(int j=1;j<=n;j++)
		 if(!b[j]&&(m[j]<m[k]))
		  k=j;
		b[k]=1;
		for(int j=1;j<=n;j++)
		 if(!b[j]&&(a[k][j]<m[j]))
		  m[j]=a[k][j];   
	}  
	for(int i=1;i<=n;i++)
	 s+=m[i];
	cout<<setprecision(2)<<fixed<<s;//保留两位小数
}

kruskal

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int n,o,v[105];
double m,s,x[105],y[105],a[105][105];
int main()
{
   
	cin>>n;
	for(int i=1;i<=n;i++)
	{
   
		cin>>x[i]>>y[i];
	    for(int j=1;j<n;j++)
		{
   
	    	a[i][j]=sqrt((abs(x[i]-x[j]))*(abs(x[i]-x[j]))+(abs(y[i]-y[j]))*(abs(y[i]-y[j])));//距离
	    	a[j][i]=a[i][j];//将距离也赋值给a[j][i]
		}
	} 
	for(int i=1;i<=n;i++)v[i]=i;  下面套模板
	for(int k=1;k<=n-1;k++)
  	 {
   
		int x1=0,y1=0;
      	m=2147483647;
      	for(int i=1;i<=n;i++)
     	for(int j=1;j<=n;j++)
      	 if((v[i]!=v[j])&&(a[i][j]<m)&&(a[i][j]!=0))
	   	  {
   m=a[i][j];x1=i;y1=j;}
      	s+=m;
      	double t=v[y1];
      	for(int i=1;i<=n;i++)
         if(v[i]==t)v[i]=v[x1];
	  }
  	cout<<setprecision(2)<<fixed<<s;//保留两位
}

谢谢