题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1162

【题目大意】

给你n个点的坐标，让你找到联通n个点的一种方法。保证联通的线路最短，典型的最小生成树问题。

方法一 。 通过不断找到最小的边来找到终于结果。

Kruskal 算法

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cmath>

using namespace std;

struct node{

    double a,b;

    int po;

}point[110];

const int maxe = 10010;

struct Edge{

    int v1,v2;

    double length;

}edge[maxe];

bool cmp(const Edge&a, const Edge&b){

    return a.length<b.length;

}

int n; int cnt;

int father[110];

void MakeSet(){

    for(int i=0;i<=n;i++){

        father[i]=i;

    }

}

int Find(int x){

    int xroot = x;

    while(xroot!=father[xroot])

        xroot=father[xroot];

    while(x!=xroot){

        int tmp = father[x];

        father[x]=xroot;

        x = tmp;

    }

    return xroot;

}

void Union(int x,int y){

    int xr=Find(x);

    int yr=Find(y);

    if(xr==yr) return ;

    else{

        father[xr]=yr;

    }

}

void Kruskal(){

    int edgenum=0;

    double ans=0;

    for(int i=0;i<cnt&&edgenum!=n-1;i++){

        if(Find(edge[i].v1)!=Find(edge[i].v2)){

            ans+=edge[i].length;

            Union(edge[i].v1,edge[i].v2);

            edgenum++;

        }

    }

    printf("%.2lf\n",ans);

}

double disc(node x, node y){

    return (double)sqrt((x.a-y.a)*(x.a-y.a)+(x.b-y.b)*(x.b-y.b));

}

int main(){

    double a,b;

    while(cin>>n){

        for(int i=0;i<n;i++){

            cin>>point[i].a>>point[i].b;

            point[i].po=i+1;

        }

        MakeSet();

        cnt=0;

        for(int i=0;i<n;i++){

            for(int j=i+1;j<n;j++){

                double dis= disc(point[i],point[j]); //求出点 与 点 之 间 的距 离， 列出全部的边。

edge[cnt].v1=point[i].po;

                edge[cnt].v2=point[j].po;

                edge[cnt].length=dis;

                cnt++;

            }

        }

        sort(edge,edge+cnt,cmp);

        Kruskal();

    }

    return 0;

}

方法二 prim算法， 通过不断找到距离 最小生成树所在集合全部点中 距离最小的点。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

#define maxn 110

#define INF 0xfffffff

struct node{

	double a,b;

	int po;

}point[maxn];

int n;

struct node2{

	int v;

	double dis;

	node2(int v=0, double dis=0):v(v),dis(dis){}

};

vector <node2> G[maxn]; //用邻接链表储存图

const int maxe = 10010;

bool intree[maxn];

double minDist[maxn];

void init(){

	for(int i=0;i<maxn;i++ ){

		minDist[i]=INF;

		G[i].clear();

		intree[i]=false;

	}

}

double prim(int s){

	intree[s] = true;

	for(int i=0;i<G[s].size();i++){

		int vex = G[s][i].v;

		minDist[vex] = G[s][i].dis; //初始化  ， 将与起点相联的 点与起点的距离“显化”

	}

	double ans = 0;

	for(int nodeNum = 1 ;nodeNum<=n-1;nodeNum++){ //还剩下 n-1 个点未找

		double tmpMin = INF;

		int addNode;

		for(int i=1;i<=n;i++){

			if(!intree[i]&&minDist[i]<tmpMin){ //仅仅有经过显化的 且没有入最小生成树的点 才干通过比較

				tmpMin = minDist[i]; //不断更新，找到最短的

				addNode = i;

			}

		}

		intree[addNode] = true; //入树

		ans+=tmpMin;

		for(int i=0; i < G[addNode].size();i++){ //更新  将新增加节点的 相联节点“显化”

			int vex = G[addNode][i].v;

			if(!intree[vex]&&G[addNode][i].dis<minDist[vex]) //更新未入最小生成树的节点，与之的最短距离。

				minDist[vex] = G[addNode][i].dis;

		}

	}

	return ans;

}

double disc(node x, node y){

	return (double)sqrt((x.a-y.a)*(x.a-y.a)+(x.b-y.b)*(x.b-y.b));

}

int main(){

	double a,b;

	while(cin>>n){

		for(int i=0;i<n;i++){

			cin>>point[i].a>>point[i].b;

			point[i].po=i+1;

		}

		init();

		for(int i=0;i<n;i++){

			for(int j=i+1;j<n;j++){

				double dis= disc(point[i],point[j]);

				G[point[i].po].push_back(node2(point[j].po,dis));

				G[point[j].po].push_back(node2(point[i].po,dis));

			}

		}

		double ans = prim(1);

		printf("%.2lf\n",ans);

	}

	return 0;

}