HDOJ 1162:Eddy's pictureは最小生成ツリーを解く.


http://acm.hdu.edu.cn/showproblem.php?pid=1162
    この問題も単純に最小生成樹の問題を解決するための濃密図であり、プリムアルゴリズムの応用の場である.完全図では、プリムアルゴリズムの複雑さ(n^2)は、クルーズカードアルゴリズムの複雑さ(n^2 logn^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
", sum); } system("pause"); return 0; }