本文主要是介绍【01规划】POJ 2728 Desert King，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 2728 Desert King
题意：给出 n 个点的坐标和它的高度，求一颗生成树使得树上所连边的两点高度差之和除以距离之和最小。
思路：同样构造f(l)方程， 令∑hight / ∑dis = l，那么∑hight = l*∑dis, 令f(l) = ∑(hight - l*dis) ,题目所求是最小值 那么∑hight / ∑dis ≤ l 说明存在更优解，即f(l) ≤ 0 ，二分 l 得出答案
关于f(l)和二分边界判断 ：
我们设 cost = hight - l*dis ,把它当做边求最小生成树，那么求得的f(l) 必定为最小，由此确定二分边界
求最小生成树时尽量用prime，kruskal不太好操作（其实是我不会）
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
double g[N][N],hight[N][N];
double dis[N];
double x[N],y[N],r[N];
int n;
double dist(int i,int j){double t=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);return sqrt(t);
}
bool st[N];
double prime(double mid){memset(st,false,sizeof st);double sum=0;for(int i=1;i<=n;i++) dis[i]=1e15;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dis[t]>dis[j])) t = j;}st[t]=true;if(i) sum+=dis[t];for(int j=1;j<=n;j++){dis[j]=min(dis[j],hight[t][j]-g[t][j]*mid);}}return sum;
}
int main(){while(cin>>n){if(!n) return 0;for(int i=1;i<=n;i++){cin>>x[i]>>y[i]>>r[i];for(int j=1;j<=i;j++){g[i][j]=g[j][i]=dist(i,j);hight[i][j]=hight[j][i]=fabs(r[j]-r[i]);}}double l=0,r=1e5,mid;while(r-l>1e-6){mid=(l+r)/2.;if(prime(mid)<0) r=mid; else l=mid;}printf("%.3lf\n",mid);}return 0;
}
这篇关于【01规划】POJ 2728 Desert King的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
