#include <iostream>
#include <math.h>
#include <vector>
#include <float.h>
#include <iomanip>
using namespace std;

struct node
{
//public:
	float x,y;
	float distance;
	float dis(node a) //储存与S里所有元素的距离中最小的
	{
		return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y));
		
	}
};
node m,p;
vector<node> v;  //集合S
vector<node> vv;  //集合S`
float ans;
int n;
void prim();
int main()
{

	while(cin>>n)
	{
		int i;
		while(!v.empty())
		{
			v.pop_back();
		}
		for(i=0;i<n-1;i++)
		{
			scanf("%f%f",&m.x,&m.y);
			m.distance=FLT_MAX;
			vv.push_back(m);
		}
		scanf("%f%f",&m.x,&m.y);
		m.distance=FLT_MAX;
		v.push_back(m);
				
		prim();
		cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
	}
	return 0;
}

void prim()
{
	int i,j;
	for(i=0;i<n-1;i++)
	{
		vv[i].distance = vv[i].dis(v[0]);
	}	
	ans=0;
	v[0].distance=FLT_MAX;
	for(i=0;i<n;i++)
	{
		
		int k=0;
		float min=FLT_MAX;
		for(j=0;j<vv.size();j++)
			if(vv[j].distance<min)
			{
				k=j;
				min=vv[j].distance;
			}
		if(min==FLT_MAX) break;
		v.push_back(vv[k]);
		vv.erase(vv.begin()+k);

		ans+=v.back().distance;

		for(j=0;j<vv.size();j++)
			if(vv[i].dis(v.back())<vv[i].distance)
				vv[i].distance=vv[i].dis(v.back());
	}
}

• Re:谁能帮找下错吗 或者给我些数据我测试一下 不知道错哪了 总wa (38) aa2650 2009-08-25 20:53:23