prime+邻接矩阵模板
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 110
struct Node//定义点
{
double x,y;
} node[MAXN];
double cost[MAXN][MAXN];//耗费矩阵
double distance(Node a,Node b)//两点的距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//***********************************************************************
//套用prim模板
//***********************************************************************
#define typec double
const double INF=0x3f3f3f3f;
int vis[MAXN];//已经找过的点
double lowc[MAXN];//未遍历集合中的点到已遍历的最近距离
double prim(double cost[][MAXN],int n)//点从0~n-1
{
int i,j,p;
double minc,res=0;
memset(vis,0,sizeof(vis));
vis[0]=1;
for(i=1; i<n; i++) lowc[i]=cost[0][i];
for(i=1; i<n; i++)//最小树上一共有n-1条边
{
minc=INF;//最小距离
p=-1;//记录最小点位
for(j=0; j<n; j++)
if(vis[j]==0&&minc>lowc[j])
{
minc=lowc[j];
p=j;
}
if(minc==INF)return -1;//原图不连通
res+=minc;
vis[p]=1;
for(j=0; j<n; j++)//只要更新这个点对应的相接点的距离就行
if(vis[j]==0&&lowc[j]>cost[p][j])
lowc[j]=cost[p][j];
}
return res;
}
//********************************************************************
int main()
{
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
scanf("%lf%lf",&node[i].x,&node[i].y);
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(i==j)cost[i][j]=0;
else
cost[i][j]=distance(node[i],node[j]);
}
}
printf("%.2lf\n",prim(cost,n));
}
return 0;
}