/**//* 目标:min{∑costi/∑leni} 逼近的思想,∑costi/∑leni<=x,即 ∑(costi-x*leni)<=0 是一个单调递减函数 即求边为costi-x*leni的 MST 可以用二分,但比较慢 用迭代快好多 */ #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std;
const double esp=0.00001; const int MAXN=1010; const double DINF=1000000000.0;
struct Point{ int x,y,z; }points[MAXN];
int N; bool vi[MAXN]; double dist[MAXN]; int pre[MAXN];
double cal(int a,int b){ return sqrt(1.*(points[a].x-points[b].x)*(points[a].x-points[b].x)+ 1.*(points[a].y-points[b].y)*(points[a].y-points[b].y)); }
double prim(double x){ memset(vi,0,sizeof(vi)); for(int i=2;i<=N;i++){ dist[i]=abs(points[1].z-points[i].z)-cal(1,i)*x; pre[i]=1; } dist[1]=0;vi[1]=1; double cost=0,len=0; for(int i=1;i<N;i++){ double Min=DINF; int u; for(int j=2;j<=N;j++) if(!vi[j]&&Min>dist[j]){ Min=dist[j]; u=j; } vi[u]=1; cost+=abs(points[pre[u]].z-points[u].z); len+=cal(pre[u],u); for(int j=2;j<=N;j++){ double val=abs(points[u].z-points[j].z)-cal(u,j)*x; if(!vi[j]&&dist[j]>val){ dist[j]=val; pre[j]=u; } } } return cost/len; } int main(){ while(scanf("%d",&N),N){ for(int i=1;i<=N;i++) scanf("%d%d%d",&points[i].x,&points[i].y,&points[i].z); //分数规划用:Dinkelbach算法 //每次迭代子问题的解cost`/len`进去,这样会不断逼近最优解 double a=0,b; while(1){ b=prim(a); if(fabs(b-a)<esp)break; a=b; } printf("%.3f\n",b); } return 0; }
/**//* //cost-len*x<=0 double low=0,high=100.0; //其实二分20多次已经很足够了 while(high-low>esp){ double mid=(low+high)/2; if(prim(mid))high=mid; else low=mid; } printf("%.3f\n",high);
*/
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|