题目链接：http://poj.org/problem?id=2728
题意是给出n个点的x，y，z值，要将n个点通过边连接起来。两个点之间的价值w是两点之间的平面欧几里德距离，费用c是两点直接的z坐标差。要求∑c/∑w的最小值。
意思就是要求一个价值和费用比最高的生成树。
题目要求的就是最小的r = ∑c/∑w
我们可以构造一个这样的子问题，求z(k) = ∑c – k * ∑w
由于运算的性质，我们可以转化成：z(k) = ∑(ci – k * wi)
这样一来，求z(k)的最小值的问题就能够转化为求边i的权值为ci - k * wi的最小生成树的问题了。
同时函数z满足单调减，因为k越大，每个点的价值越小。
同时能过推出让r最小的k值minr满足：z(minr) = 0。这个结论是很好证明的。
那么我们现在就是要找到一个k值使得z(k) = 0。
下面的事情就简单了。我采取的是二分答案的做法，事实上从0~100进行25次二分就能够找到足够精确的答案。（20次二分不行……会WA，别问我怎么知道的）
循环控制可以是mark++<25也可以是r– l > 1e-5
PS：貌似最大生成树使用kruskal会导致TLE，推荐使用prim算法。
AC代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #define MAXN 1005 #define MAXE 1000005 #define EPS 1e-7 using namespace std; const double MaxDouble=100000007.0; double map[MAXN][MAXN];//邻接表 double cost[MAXN][MAXN]; double lowcost[MAXN];//最短距离 int vis[MAXN];//是否访问过 int n; struct point { int x; int y; int z; }p[MAXN]; double dis(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)); } int sign(double x) { if(fabs(x)<EPS) return 0; else return x<0?-1:1; } double prim(int seed,double k)//参数seed: 初始随机选择的起始点编号 { double minn,res=0; int i,j,pos; memset(vis,0,sizeof(vis));//初始化访问状态 vis[seed]=1;pos=seed;//设置初始节点 for(i=0;i<n;i++) lowcost[i]=cost[pos][i]-k*map[pos][i];//第一次更新lowcost for(i=0;i<n-1;i++)//连n-1条边 { minn=MaxDouble;//初始化 for(j=0;j<n;j++) { if(vis[j]==0&&lowcost[j]<minn)//遍历所有节点，寻找lowcost最小的点 { minn=lowcost[j]; pos=j; } } res+=minn;//答案增加 vis[pos]=1;//更新访问状态 for(j=0;j<n;j++) { double temp=cost[pos][j]-k*map[pos][j]; if(vis[j]==0&&lowcost[j]>temp)//根据新的节点更新lowcost值 lowcost[j]=temp; } } return res; } int del(int x) { return x>0?x:-x; } int main() { int i,j,a,b; while(cin>>n,n) { for(i=0;i<n;i++)//读入&处理 scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z); for(i=0;i<n;i++) for(j=0;j<i;j++) { map[i][j]=map[j][i]=dis(i,j); cost[i][j]=cost[j][i]=del(p[i].z-p[j].z); } double l=0.0,r=100.0,mid; int mark=0; while(mark++<25)//进行25次二分 { mid=(l+r)/2; if(sign(prim(0,mid))>=0) l=mid; else r=mid; } printf("%0.3f\n",r); } }
