/*
 *Descripttion: 2349 Arctic Network
 *				It seems that this problem is a MST problem
 *More :	Prim algorithm
 *Author : BlueBlood --	RTFSC
 *Time: 2005 - 12- 09
 */

#include <iostream>
#include <cstdlib>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAXWEIGHT 32767

typedef struct{
	int vi;		//head of a edge
	int vj;		//tail of a edge
	double weight;	
} edge;

int s;
int p;
double d;
int * x;
int * y;
double ** adj;
double *res;
edge *T;

void Prim( void )
{
	int m;
	int v;
	int nmin;
	double dis;

	edge e;

	//Initializing T;
	for (int j = 1; j < p; j++)
	{
		T[j-1].vi = 1;
		T[j-1].vj = j + 1;
		T[j-1].weight = adj[0][j];
	}

	//find out the k+1 th MST's edge
	for (int k = 0; k < p - 1; k++)
	{
		nmin = MAXWEIGHT;

		//find the edge with the smallest weight from T[k],..., T[n-2] to join the MST;
		for (j = k; j < p - 1; j++)
		{
			if (T[j].weight < nmin)
			{
				nmin = T[j].weight;
				m = j;
			}
		}
		

		//Exchange T[m] & T[k];
		e = T[m]; 
		T[m] = T[k];
		T[k] = e;

		//v is the number of the vertex newly added to MST
		v = T[k].vj;

		//Modify T[k + 1], T[k + 2],..., T[n - 1];
		for (j = k + 1; j < p - 1; j++)
		{
			dis = adj[v-1][T[j].vj - 1];

			if ( d < T[j].weight)
			{
				T[j].weight = dis;
				T[j].vi  = v;
			}
		}

	}
}

int main()
{
	int testCase;
	int i;
	int j;
	int k;
	
	cin >> testCase;

	for ( i = 0;  i < testCase; i++)
	{
		cin >> s >> p;

		x = new int [p];
		y = new int [p];
		adj = new double * [p];
		res = new double [p];
		T = new edge [p];

		for (j = 0; j < p; j++)
		{
			cin >> x[j] >> y[j];
			adj[j] = new double [p];
		}

		for (j = 0; j < p; j++)
			for (k = 0; k < p; k++)
			{
				if (k == j)
					adj[j][k] = MAXWEIGHT;
				else
					adj[j][k] = sqrt( (x[j] - x[k])*(x[j] - x[k]) + (y[j] - y[k])*(y[j] - y[k]));
			}


		Prim();

		for ( i = 0; i < p - 1 ; i++)
		{
			res[i] = T[i].weight;
		}

		sort(&res[0], & res[p-1]);

		printf("%.2f\n",res[p-1-s]);

	}

	system("pause");
	return 0;
}

• Re:我用的Prim求最小生成树,WA,是题目理解错了呢，还是程序有bug?" (2432) alpc03 2005-12-11 09:15:49
• me too (0) alpc03 2005-12-11 09:16:26
• 看不懂题，例题也不懂＾晕死了＾为什么不是200.00＾是不是把两个satellite分给某两个outpost,然后…… (0) alpc02 2005-12-13 20:18:12
  • 然后，他们就“入党”了。 (0) Judas 2005-12-13 20:41:43
    • Re:然后，他们就“入党”了。//？ (0) alpc02 2005-12-14 13:29:00
      • Re:然后，他们就“入党”了。//？ (0) xujiaming 2008-07-23 13:22:21