这个题的意思是给你一个连通图， 图上每个点都有连个权值ai, bi让你选一个生成树使得sigma(ai*xi)/sigma(bi*xi)最小， 对比与基础的01规划， 我们假设答案是mid， 然后建立一个图， 其新的边的权值是ai-mid*bi, 然后求解最小生成树，假设其答案是tp, 如果tp>=0，说明还有更优的解， 如果小于0那么解小于mid, 代码如下：
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> 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<n; i++) for(int j=i; j<n; j++) { ci[i][j] = ai[i][j] - mid*bi[i][j]; ci[j][i] = ci[i][j]; if(i==j) ci[i][j] = (double)inf; } for(int i=0; i<n; i++) { mincost[i] = (double)inf; used[i] = false; } mincost[0] = 0; double res = 0; while(true) { int v = -1; for(int u=0; u<n; u++) if(!used[u] && (v==-1||mincost[u]<mincost[v])) v=u; if(v == -1) break; used[v] = true; res += mincost[v]; for(int u=0; u<n; u++) mincost[u] = min(mincost[u], ci[v][u]); } return res; } int main() { while(scanf("%d", &n)==1 && n) { for(int i=0; i<n; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); vi[i] = (Vi){x, y, z}; } double high = 0.0; for(int i=0; i<n; i++) for(int j=i; j<n; j++) { ai[i][j] = abs(vi[i].z-vi[j].z); ai[j][i] = ai[i][j]; bi[i][j] = dist(i, j); bi[j][i] = bi[i][j]; high += ai[i][j]; } double l=0.0, r=high+5.0; while(r-l >= eps) { double mid = (l+r)/2.0; double tp = check(mid); //printf("l=%.3f, r=%.3f, mid=%.3f, tp=%.3f ", l, r, mid, tp); if(tp>=0.0) l=mid; else r=mid; } printf("%.3f ", l); } return 0; }