01分数规划

求解$\frac{\sum{A_iX_i}}{\sum{B_iX_i}}\ (X_i\in\{0,1\})$的最小值，并且有某些奇怪的限制。

我们把$X_i=1$的提取出来

我们可以二分一个答案$mid$，如果答案的最小值小于等于$mid$，那么有$\frac{\sum A_i}{\sum B_i}\le mid$

可以化简为$\sum \{A_i - mid*B_i\} \le 0$，只需判断是否有符合条件的$A_i、B_i$序列即可

例题 POJ 2728

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1020;
const double eps = 1e-5; // 开太大会WA，太小(如1e-6)会TLE
double dist[N][N], cur_dist[N], x[N], y[N], w[N];
bool vis[N];
int n;

inline double calc_dist(int i, int j){
    return sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]));
}

double prim(double ans){
    memset(vis, 0, sizeof vis);
    vis[0] = 1;
    double sum = 0;
    for(int i=1; i<n; i++) cur_dist[i] = fabs(w[0]-w[i]) - ans*dist[0][i];
    for(int i=1; i<n; i++){
        int most = -1;
        double extreme;
        for(int j=1; j<n; j++){
            if(vis[j]) continue;
            if(most == -1 || extreme > cur_dist[j]){
                most = j;
                extreme = cur_dist[j];
            }
        }
        vis[most] = 1;
        sum += cur_dist[most];
        for(int j=1; j<n; j++){
            if(vis[j]) continue;
            cur_dist[j] = min(cur_dist[j], fabs(w[j]-w[most]) - ans*dist[j][most]);
        }
    }
    return sum;
}

void solve(){
    for(int i=0; i<n; i++) scanf("%lf%lf%lf", &x[i], &y[i], &w[i]);
    for(int i=0; i<n; i++){
        for(int j=i; j<n; j++)
            dist[i][j] = dist[j][i] = calc_dist(i, j);
    }
    double l=0, r=100, mid; // 理论上r=100是不对的，但是这题开太大会TLE
    while(r-l > eps){
        mid = (l + r) / 2;
        if(prim(mid) <= 0){
            r = mid;
        }else{
            l = mid;
        }
    }
    printf("%.3f\n", l); // 很邪门，用%.3lf会WA
}

signed main(){
    while(scanf("%d", &n) == 1 && n) solve();
}