题目链接：?id=2728
题意：给出几个村庄的坐标x[i]和y[i]，以及海拔z[i]。要在这些村庄之间建水渠，，费用和两个村庄的海拔差成正比，水渠长度和村庄二维坐标（x,y）上的距离成正比，要求一种方案使得(总的花费/总的水渠长度)最小，输出这个最小值，保留三位小数。
这是一道0，1分数规划的题目，求的是一棵生成树sigma(dh)/sigma(l) 的最小值（dh是树上两点之间的高度差，l是树上两点之间的边长）。
按0，1分数规划的思路对解进行分析：(设解为R)，有sigma(dh)-R*sigma(l)=0, 假设X不是最优解即不能使得(总的花费/总的水渠长度)最小，比R要大一点，那么最优比率生成树使得sigma(dh)/sigma(l) < X，也就是sigma(dh)-X*sigma(l)<0即sigma(dh-X*l)<0所以把两点间的权用dh-X*l来表示，所以必有一棵最小生成树使得生成树的权和<0。同理若X>R，则必有一棵最小生成树使得生成树的权和>0。
所以可以二分出答案。
因为这题是完全图，而且时间卡的很紧，一般用kruskal都T了，而且prim用堆优化也有很多T了，prim+堆复杂度是O( |E|log|V| ),
是完全图所以复杂度是O( V^2log|V| )反而比裸的primO(V^2)要大。
所以这是TLE的代码：
// 各种TLE …#include<cstdio>#include<queue>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<vector>#define inf 0x7fffffffusing namespace std;struct node{int x,y,h;};typedef pair<double,int >P;priority_queue<P,vector<P>,greater<P> >que;node point[1100];int n;double dis[1100];bool vis[1100];void ini(){for(int i=1;i<=n;i++){scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].h);}}double dist(int u,int v,double x){double dx=point[u].x-point[v].x,dy=point[u].y-point[v].y;double ans=abs(point[u].h-point[v].h)-x*sqrt(dx*dx+dy*dy);return ans;}bool ok_prim(double x){memset(vis,0,sizeof(vis));fill(dis,dis+n+1,inf);double res=0;dis[1]=0;que.push(P(0,1));while(!que.empty()){P p=que.top();que.pop();int u=p.second;if(vis[u]) continue;vis[u]=1;res+=dis[u];for(int i=1;i<=n;i++){if(vis[i]) continue;double tmp=dist(u,i,x);if(dis[i]>tmp){dis[i]=tmp;que.push(P(dis[i],i));}}}return res>=0;}void solve(){double lb=0,ub=1e5;while(ub-lb>1e-4){double mid=(lb+ub)/2;if(ok_prim(mid)) lb=mid;else ub=mid;}printf("%.3f\n",lb);}int main(){while(~scanf("%d",&n)&&n){ini();solve();}return 0;}用裸的prim二分才刚好过：//Accepted724K2438MS#include<cstdio>#include<queue>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<vector>#define inf 9999999999using namespace std;struct node{int x,y,h;};node point[1100];int n;double dis[1100];bool vis[1100];void ini(){for(int i=1;i<=n;i++){scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].h);}}double dist(int u,int v,double x) // 求两点间dh-X*l的边权 {double dx=point[u].x-point[v].x,dy=point[u].y-point[v].y;double ans=abs(point[u].h-point[v].h)-x*sqrt(dx*dx+dy*dy);return ans;}bool ok_prim(double x){memset(vis,0,sizeof(vis));fill(dis,dis+n+1,inf);double res=0;dis[1]=0;while(true){int v=-1;for(int u=1;u<=n;u++){if(!vis[u]&&(v==-1||dis[u]<dis[v])) v=u;}if(v==-1) break;vis[v]=1;res+=dis[v];for(int u=1;u<=n;u++){if(vis[u]) continue;dis[u]=min(dis[u],dist(v,u,x));}}return res>=0;}void solve(){double lb=0,ub=1e7;while(ub-lb>1e-4){ //二分double mid=(lb+ub)/2;if(ok_prim(mid)) lb=mid;else ub=mid;}printf("%.3f\n",lb);}int main(){while(~scanf("%d",&n)&&n){ini();solve();}return 0;}可以看出二分的效率实在不高，0，1规划还有另一个算法Dinkelbach算法，类似于牛顿迭代法。算法的具体过程是：随便假设一个X1解（比如假设的这个解比最优解大），然后用同样的思路去求最小生成树，肯定会得到边权和<0，所以不是最优解，但这不是最终的目的，还需要用到这棵生成树，题目让我们求要求一种方案使得(总的花费/总的水渠长度)最小解，所以算出按这棵生成树的方案得到的解X2，这个解必定更靠近最优解（因为这棵树使得sigma(dh)/sigma(l) < X1，所以比X1要优），所以再用X2去求dh-X*l的最小生成树，再按这棵树的方式得到更优解X3,迭代多次后Xn，Xn-1与最优解相差无几，所以Xn-Xn-1<ESP，就求得了最优解。
以上这是这个算法的正确性的认识，但是复杂度的证明很复杂。但是比二分要优。
//732K344MS#include<cstdio>#include<queue>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<vector>using namespace std;struct node{int x,y,h;};node point[1100];int n;double dis[1100];int pre[1100];bool vis[1100];void ini(){for(int i=1;i<=n;i++){scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].h);}}double dist(int u,int v,double x){double dx=point[u].x-point[v].x,dy=point[u].y-point[v].y;double ans=abs(point[u].h-point[v].h)-x*sqrt(dx*dx+dy*dy);return ans;}double prim(double x){memset(vis,0,sizeof(vis));double sh=0,sl=0;dis[1]=0;vis[1]=1;for(int i=2;i<=n;i++){dis[i]=dist(1,i,x);pre[i]=1;}while(true){int v=-1;for(int u=1;u<=n;u++){if(!vis[u]&&(v==-1||dis[u]<dis[v])) v=u;}if(v==-1) break;vis[v]=1;sh+=abs(point[v].h-point[pre[v]].h);double dx=point[pre[v]].x-point[v].x,dy=point[pre[v]].y-point[v].y;sl+=sqrt(dx*dx+dy*dy);for(int u=1;u<=n;u++){if(vis[u]) continue;double tmp=dist(v,u,x);if(dis[u]>tmp){dis[u]=tmp;pre[u]=v;}}}return sh/sl;}void solve(){double a=0,b=0;//随便设一个解0while(1){b = prim(a); //迭代if(fabs(a-b)<1e-7) break;a=b; //迭代}printf("%.3f\n",b);}int main(){while(~scanf("%d",&n)&&n){ini();solve();}return 0;}
临行之前，面对太多的疑问和不解：为何是一个人？
