最优比率生成树 11WA

比率生成树 11WA"/>

最优比率生成树 11WA

最优比率生成树

什么是最优比率生成树？

第一次接触到是，poj 2728.

用途：求类似于=∑(benifit[i]) / ∑(cost[i])的比例问题时，即01规划问题时，求最大(小）比率。

源代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
#define maxn 1001
using namespace std;struct node{
int x,y;
double h;}vil[maxn];int n;
double cost[maxn][maxn],dist[maxn][maxn],d[maxn],vis[maxn];
double ans;double ratio_mst(double date);double solve();int main()
{while(scanf("%d",&n),n){int x,y;double h;for(int i=1;i<=n;i++){scanf("%d%d%lf",&x,&y,&h);vil[i].x=x;vil[i].y=y;vil[i].h=h;}for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++){dist[i][j]=dist[j][i]=sqrt(fabs(double((vil[i].x-vil[j].x)*(vil[i].x-vil[j].x)+(vil[i].y-vil[j].y)*(vil[i].y-vil[j].y))));   ///错误11次贡献处cost[i][j]=cost[j][i]=fabs(vil[i].h-vil[j].h);}printf("%.3lf\n",solve());}return 0;
}double ratio_mst(double date)
{ans=0;for(int i=2;i<=n;i++){d[i]=cost[1][i]-date*dist[1][i];vis[i]=0;}vis[1]=1;d[1]=0;int ij=1;for(int i=1;i<n;i++){int k,j;double mi=INF;for(k=1;k<=n;k++){if(!vis[k]&&mi>d[k]){mi=d[k];ij=k;}}vis[ij]=1;ans+=d[ij];for(j=1;j<=n;j++){if(!vis[j])d[j]=min(d[j],cost[ij][j]-date*dist[ij][j]);}}return ans;}double solve()
{double down=0,up=1e6;double mid;for(int i=1;i<=50;i++){mid=(up+down)/2;if(ratio_mst(mid)<0)up=mid;elsedown=mid;}return (down+up)/2;}