最优比率生成树 #include<iostream>#include<cmath>#include<iomanip>#include<string.h>const int MAX=1005;const int inf=0x7fffffff;using namespace std;int n;double x[MAX],y[MAX],z[MAX],cost[MAX][MAX],

poj2728 Desert King 大概题意：   每两个点中的边权有两个：一个是两点坐标的欧几里得距离（ horizontal distance），暂且成为ai,第二个是两点的海拔之差，称为bi.然后需要一个生成树使sum(ai)\sum(bi)最小。   这里可以引入分数规划：我们设ai\bi=k,那么ai-bi*k=0 我们只需要二分一个值mid，当ai-bi*mid=0时，