POJ 2560 Freeckles Prime問題解決アルゴリズム

この問題は最小生成樹を求めています.
ノードの座標を指定すると、各点間のこれらの座標から距離を計算する必要があります.
これ以外は標準的なPrimeアルゴリズムであり、基本的にはPrimeを利用して、Kruskyalを使用することができます.
経典の計算方法は必ず記入して、熟練度.さもなくば、それは非常に難しい利用です.
しかも経典の計算方はなぜ経典ですか?その理由の一つは、自分で勝手に想像していないからです.

#include <stdio.h>
#include <string.h>
#include <queue>
#include <float.h>
#include <algorithm>
#include <math.h>
using namespace std;

struct Point
{
	float x, y;
};
const int MAX_N = 101;
Point P[MAX_N];
bool vis[MAX_N];
float dist[MAX_N];
float minDist[MAX_N];

float calDist(Point &a, Point &b)
{
	float x = a.x - b.x;
	float y = a.y - b.y;
	return sqrtf(x*x + y*y);
}

void Prime(int n)
{
	memset(vis, 0, sizeof(bool) * (n+1));
	vis[1] = true;
	dist[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		dist[i] = calDist(P[1], P[i]);
	}
	
	for (int i = 1; i < n; i++)
	{
		float minD = FLT_MAX;
		int id = 0;
		for (int j = 2; j <= n; j++)
		{
			if (!vis[j] && dist[j] < minD)
			{
				minD = dist[j];
				id = j;
			}
		}
		vis[id] = true;
		minDist[i] = minD;
		for (int j = 2; j <= n; j++)
		{
			if (!vis[j])
			{
				float d = calDist(P[id], P[j]);
				if (d < dist[j]) dist[j] = d;
			}
		}
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%f %f", &P[i].x, &P[i].y);
	}
	Prime(n);
	float ans = 0.f;
	for (int j = 1; j < n; j++)
	{
		ans += minDist[j];
	}
	printf("%.2f
", ans);
	return 0;
}

著作権声明:このブログのオリジナル記事.ブログは、同意なしに転載してはいけません.