POJ 2728 Desert King 01分数规划,最优比率生成树

时间:2021-06-11 12:06:14

一个完全图,每两个点之间的cost是海拔差距的绝对值,长度是平面欧式距离,

让你找到一棵生成树,使得树边的的cost的和/距离的和,比例最小

然后就是最优比例生成树,也就是01规划裸题

看这一发:http://blog.csdn.net/sdj222555/article/details/7490797

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<string.h>
using namespace std;
const int N=1e3+;
const double eps=1e-;
const int INF=0x3f3f3f3f;
int n;
double x[N],y[N],z[N];
double cost[N][N],dis[N][N];
bool vis[N];
double d[N];
double mst(double x) {
memset(vis,false,sizeof(vis));
vis[]=true;
for(int i=; i<=n; ++i) {
d[i]=cost[][i]-x*dis[][i];
}
double ret=;
for(int i=;i<n;++i){
int u;
double mx=INF;;
for(int j=;j<=n;++j)
if(!vis[j]&&mx>d[j]){
mx=d[j];
u=j;
}
ret+=mx;
vis[u]=true;
for(int j=;j<=n;++j)
if(!vis[j]&&d[j]>cost[u][j]-x*dis[u][j])
d[j]=cost[u][j]-x*dis[u][j];
}
return ret;
}
int main() {
while(~scanf("%d",&n)) {
if(n==)break;
for(int i=; i<=n; ++i) {
scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
for(int j=; j<i; ++j) {
dis[i][j]=dis[j][i]=sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
cost[i][j]=cost[j][i]=fabs(z[i]-z[j]);
}
}
double r=200000.0,l=0.0,mid;
while(r-l>eps) {
mid=(l+r)/2.0;
if(mst(mid)>=)l=mid;
else r=mid;
}
printf("%.3f\n",mid);
}
return ;
}