Posted on 2011-09-09 04:27
成幸毅 阅读(299)
评论(0) 编辑 收藏 引用
最优比例生成树,分数规划
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
//0/1分数规划满足单调性，也就是比例生成树已经确定了，只要去猜l，让他满足Z（l）等于0
const double eps = 1e-6;
int n;
struct node 
{
int x,y,z;
}v[1010];
double g[1010][1010];
double opt[1010];
bool vis[1010];
double prim() {
double minn;
memset(vis,0,sizeof(vis));
int vex = 0;
double ans = 0.0;
for(int i = 1; i <= n; i++) opt[i] = g[1][i];
vis[1] = true;
for(int i = 1; i < n; i++) {
minn = 1e9+1.0;
for(int j = 1; j <= n; j++) {
if(opt[j] < minn && !vis[j]) {
minn = opt[j];
vex = j;
}
}
vis[vex] = true;
ans += minn;
for(int j = 1; j <= n; j++) {
if(!vis[j]) {
opt[j] = opt[j] < g[vex][j]?opt[j]:g[vex][j];
}
}
}
return ans;
}
int main() {
while(scanf("%d",&n) && n) {
for(int i = 1; i <= n; i++)
for(int j =1 ; j <= n; j++)
g[i][j] = 1e9;
for(int i = 1; i <= n; i++)
scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].z);
double l = 0,r = 1000000;
double mid;
double dis,cost;
while(r - l >= eps) {
mid = (l+r)/2;
for(int i = 1;i <= n; i++)
for(int j = i + 1; j <= n; j++) {
dis = sqrt(1.0*(v[i].x - v[j].x)*(v[i].x - v[j].x) + 1.0*(v[i].y - v[j].y)*(v[i].y - v[j].y));
cost = fabs(1.0*(v[i].z - v[j].z));
g[i][j] = g[j][i] = cost - mid*dis;
}
if(prim() <= 0.0)
r = mid;
else
l = mid;
}
printf("%.3f\n",r);
}
// system("pause");
return 0;
}