poj 2728 Desert King（最优比例生成树）

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cstring>

#include <iomanip>

using namespace std;

const int maxn=1005;

const double eps=1e-6;

const double inf=0xffffffff;

struct node{

	double x,y,h;

}no[maxn];

int n;

bool visited[maxn];  

double weight[maxn][maxn],c[maxn][maxn],d[maxn][maxn];

double up,down;

double dis(node &a,node &b){

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

void creattree(int n,double r)

{

	for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

		{

			weight[i][j]=c[i][j]-r*d[i][j];

		}

}

void prime()

{

	up=0.0;down=0.0;

	memset(visited,0,sizeof(visited));

	int index;

	int pre[maxn];

	double dist[maxn];

	visited[1]=1;

	for(int i=0;i<n;i++)

	{

		dist[i]=weight[1][i];

		pre[i]=1;

	}

	for(int i=0;i<n;i++)

	{

		double mmimum=inf;

		for(int j=0;j<n;j++)

		{

			if(!visited[j]&&dist[j]<mmimum)

			{

				mmimum=dist[j];

				index=j;

			}

		}

		visited[index]=1;

		up+=c[pre[index]][index];

		down+=d[pre[index]][index];

		for(int i=0;i<n;i++)

		{

			if(!visited[i]&&weight[index][i]<dist[i])

			{

				dist[i]=weight[index][i];

				pre[i]=index;

			}

		}

	}

}

int main()

{

    while(scanf("%d",&n),n)

    {

    	for(int i=0;i<n;i++)

    	{

	    	scanf("%lf%lf%lf",&no[i].x,&no[i].y,&no[i].h);

	    }

	    for(int i=0;i<n;i++)

	    	for(int j=0;j<n;j++)

	    	{

	    		c[i][j]=fabs(no[i].h-no[j].h);

	    		d[i][j]=dis(no[i],no[j]);

	    	}

	    double r=30.0,ans=30.0;

		while(1)

		{

			creattree(n,r);

			prime();

			r=up/down;

			if(fabs(r-ans)<=eps)break;

			else ans=r;

		}

		printf("%.3lf\n",ans);

		//cout<<fixed<<setprecision(3)<<ans<<endl;

    }

}
巴特西

poj 2728 Desert King（最优比例生成树）

最新文章

热门文章
