 /**//*
目标: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
搜索
最新评论

|
|