这个题的意思是给你一个连通图， 图上每个点都有连个权值ai, bi让你选一个生成树使得sigma(ai*xi)/sigma(bi*xi)最小， 对比与基础的01规划， 我们假设答案是mid， 然后建立一个图， 其新的边的权值是ai-mid*bi, 然后求解最小生成树，假设其答案是tp, 如果tp>=0，说明还有更优的解， 如果小于0那么解小于mid, 代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int inf = 0x3fffffff;const double eps = 1e-6;const int maxn = 1000+10;int n;struct Vi{    int x, y, z;}vi[maxn];double ai[maxn][maxn], bi[maxn][maxn];double ci[maxn][maxn];double dist(int i, int j){    return sqrt((vi[i].x-vi[j].x)*(vi[i].x-vi[j].x)+(vi[i].y-vi[j].y)*(vi[i].y-vi[j].y));}double mincost[maxn];bool used[maxn];double check(double mid){    for(int i=0; i
         
          = eps)        {            double mid = (l+r)/2.0;            double tp = check(mid);            //printf("l=%.3f, r=%.3f, mid=%.3f, tp=%.3f\n", l, r, mid, tp);            if(tp>=0.0) l=mid;            else r=mid;        }        printf("%.3f\n", l);    }    return 0;}