程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2349 Arctic Network 最小生成樹題解

POJ 2349 Arctic Network 最小生成樹題解

編輯:C++入門知識

本題也是使用Prime和Kruskal都可以的最小生成樹的題解。

本題一點新意就是:需要除去最大的S-1個距離,因為可以使用衛星覆蓋這些距離。

技巧:建圖建有向圖,速度快點,不用計算兩邊。

這裡使用Prime,因為是稠密圖。


#include 
#include 
#include 
#include 
#include 
#include 
using std::sort;

const int MAX_VEC = 501;
struct Pos
{
	int x, y;
};

float gra[MAX_VEC][MAX_VEC];
Pos pos[MAX_VEC];
float dist[MAX_VEC];
bool vis[MAX_VEC];
int N, S, P;

float Prime()
{
	memset(vis, 0, sizeof(bool) * P);
	vis[0] = true;
	for (int i = 0; i < P-1; i++)
	{
		float m = (float)INT_MAX;
		int id = 0;
		for (int j = 0; j < P; j++)
		{
			if (!vis[j] && gra[0][j] < m)
			{
				m = gra[0][j];
				id = j;
			}
		}
		vis[id] = true;
		dist[i] = m;
		for (int j = 0; j < id; j++)
		{
			if (!vis[j] && gra[0][j] > gra[j][id]) gra[0][j] = gra[j][id];;
		}
		for (int j = id+1; j < P; j++)
		{
			if (!vis[j] && gra[0][j] > gra[id][j]) gra[0][j] = gra[id][j];
		}
	}
	sort(dist, dist+P-1);
	return dist[P-1-S];
}

int main()
{	
	scanf("%d", &N);
	while (N--)
	{
		scanf("%d %d", &S, &P);
		for (int i = 0; i < P; i++)
		{
			scanf("%d %d", &pos[i].x, &pos[i].y);
		}
		for (int i = 0; i < P; i++)
		{
			for (int j = i+1; j < P; j++)
			{
				float a = float(pos[i].x - pos[j].x);
				float b = float(pos[i].y - pos[j].y);
				gra[i][j] = sqrtf(a*a + b*b);
			}
		}
		printf("%.2f\n", Prime());
	}
	return 0;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved