给定整数序列a，b，求出下式的最大值
sum{ai*xi}/sum{bi*xi},xi=0|1
通俗来说，就是选出一些整数对（ai,bi），使得选出的a之和与选出的b之和商最大化
二分答案L，即选出的a之和与b之和的商是L
判断L是否成立，只要判断是否存在sum{ai-L*bi}>0即可
poj2728为要找出各边收益除以各边成本的最大生成树
那么二分商L,另边权变成ai-L*bi求最大生成树，如果和>0,答案可行
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN 1005
#define INF 1000000000
#define eps 1e-7
using namespace std;
int n;
double Edge[MAXN][MAXN],lowcost[MAXN];
int v[MAXN];
struct Point{int x, y, z;}p[MAXN]; double cal(int a, int b)
{
return sqrt(1.0 * (p[a].x - p[b].x) * (p[a].x - p[b].x) + 1.0 * (p[a].y - p[b].y) * (p[a].y - p[b].y));
}
double prim(double l)//总成本是否可以小于总长度*l ，即cost-l*len>=0，那么cost/len>=l,l得变大
{
double cost = , len = ;
double sum = ;
for(int i = ; i <= n; i++)
{
v[i] = ;
lowcost[i] = -l*abs(p[].z - p[i].z) + Edge[][i];
}
v[] = ;
for(int i = ; i < n; i++)
{
double mx = -INF;
int x = ;
for(int j = ; j <= n; j++)
if(v[j] != && lowcost[j] > mx){
x = j;
mx = lowcost[j];
} v[x] = ;
sum += lowcost[x];
for(int j = ; j <= n; j++)
{
double tmp = -l*abs(p[x].z - p[j].z) + Edge[x][j];
if(v[j] != && tmp > lowcost[j])
lowcost[j] = tmp;
}
}
if(sum>=)return ;
return ;
}
int main()
{
while(scanf("%d", &n) != EOF && n)
{
for(int i = ; i <= n; i++)
scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
Edge[i][j] = cal(i, j); double l = 0.0, r = 100.0, mid,ans;
while(r - l > 0.0000001)
{
mid = (l + r) / ;
if(prim(mid)) l = mid,ans=mid;
else r = mid;
}
printf("%.3f\n", /ans);
}
return ;
}