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;

}