本文主要是介绍poj2728，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最优比率生成树
#include<iostream>
#include<cmath>
#include<iomanip>
#include<string.h>
const int MAX=1005;
const int inf=0x7fffffff;
using namespace std;
int n;
double x[MAX],y[MAX],z[MAX],cost[MAX][MAX],dist[MAX][MAX],ans;
double prim(double mid)
{double dis[MAX];bool visit[MAX];double mini;ans=0;memset(visit,true,sizeof(visit));int i,j,num;for(i=2;i<=n;i++) dis[i]=cost[1][i]-dist[1][i]*mid;for(i=2;i<=n;i++){mini=inf;for(j=2;j<=n;j++)if(visit[j]&&mini>dis[j]){num=j;mini=dis[j];}visit[num]=false;ans+=mini;for(j=2;j<=n;j++)if(visit[j]&&dis[j]>cost[num][j]-dist[num][j]*mid)dis[j]=cost[num][j]-dist[num][j]*mid;}return ans;
}
double fun(int i,int j)
{return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{int i,j;double t;cout<<setiosflags(ios::fixed)<<setprecision(3);while(cin>>n&&n){for(i=1;i<=n;i++){cin>>x[i]>>y[i]>>z[i];for(j=1;j<i;j++){t=fun(i,j);dist[i][j]=dist[j][i]=t;cost[i][j]=cost[j][i]=abs(z[i]-z[j]);}}double l=0.0,r=1000.0,mid;while(r-l>1e-5){mid=(l+r)/2;if(prim(mid)>=0) l=mid;else r=mid;}cout<<l<<endl;}
}
这篇关于poj2728的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
