学步园

    http://acm.hdu.edu.cn/showproblem.php?pid=1162

    这道题也是一道单纯的求解最小生成树的题目，是个稠密图，所以是普里姆算法的用武之地。对于完全图，普里姆算法的复杂度（n^2）,而克鲁斯卡尔算法的复杂度（n^2logn^2），效率大小长差很大。

    我的AC代码：

#include <iostream>
#include <stdio.h>
#include <numeric>
#include <math.h>
using namespace std;

const int Max = 110;
double g[Max][Max], x[Max], y[Max];
int vers;

struct MST
{
	double dist;
	bool belong;
}Mst[Max];

void Prim()
{
	Mst[1].belong = true;

	for(int i=2; i<=vers; ++i)
	{
		Mst[i].dist = g[1][i];
		Mst[i].belong = false;
	}

	for(int i=2; i<=vers; i++)
	{
		int pos = 1;
		while(Mst[pos].belong) ++pos;
		for(int j=pos+1; j<=vers; ++j)
			if(!Mst[j].belong && Mst[j].dist < Mst[pos].dist) 
				pos = j;

		Mst[pos].belong = true;

		for(int j=1; j<=vers; ++j)
			if(!Mst[j].belong && g[pos][j] < Mst[j].dist) 
				Mst[j].dist = g[pos][j];
	}
}

double distance(double x1, double y1, double x2, double y2)
{
	return sqrt((y2-y1) * (y2-y1) + (x2-x1) * (x2-x1));
}

double add(double a, MST &b)
{
	return a + b.dist; 
}

int main()
{
	double sum;
	
	while(scanf("%d", &vers) != EOF)
	{
		for(int i=1; i<=vers; ++i) scanf("%lf %lf", x+i, y+i);
		
		for(int i=1; i<=vers; ++i)
			for(int j=1; j<=vers; ++j)
				g[i][j]= distance(x[i], y[i], x[j], y[j]);
		
		Prim();
		
		sum = accumulate(Mst+1, Mst+vers+1, 0.0, add);

		printf("%.2lf\n", sum);
	}
	system("pause");
	return 0;
}