POJ 2728 Desert King （最优比例生成树）
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;const int VM=1010;const double INF=1e15;const double eps=1e-10;struct Edge{ double x,y,z;}e[VM];int n,path[VM],vis[VM];double dist[VM][VM],cost[VM][VM],map[VM][VM],dis[VM];double Prim(double ratio){ int i,j; for(i=1;i<=n;i++){ map[i][i]=0; for(j=i+1;j<=n;j++) map[i][j]=map[j][i]=cost[i][j]-ratio*dist[i][j]; } for(i=1;i<=n;i++){ dis[i]=map[1][i]; vis[i]=0; path[i]=1; } dis[1]=0; vis[1]=1; int k; for(i=1;i<n;i++){ double tmp=INF; for(j=1;j<=n;j++) if(!vis[j] && tmp>dis[j]){ k=j; tmp=dis[j]; } vis[k]=1; for(j=1;j<=n;j++) if(!vis[j] && dis[j]>map[k][j]){ dis[j]=map[k][j]; path[j]=k; } } double c=0,d=0; for(i=1;i<=n;i++){ c+=cost[i][path[i]]; d+=dist[i][path[i]]; } return c/d;}int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n) && n){ for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&e[i].x,&e[i].y,&e[i].z); for(int i=1;i<=n;i++){ dist[i][i]=cost[i][i]=0; for(int j=i+1;j<=n;j++){ dist[i][j]=dist[j][i]=sqrt((e[i].x-e[j].x)*(e[i].x-e[j].x)+(e[i].y-e[j].y)*(e[i].y-e[j].y)); cost[i][j]=cost[j][i]=fabs(e[i].z-e[j].z); } } double r1=0,r2=0; while(1){ r2=Prim(r1); if(fabs(r1-r2)<=eps) break; r1=r2; } printf("%.3f\n",r1); } return 0;}
?
