poj2728 Desert King --- 01分数规划 二分水果。。

这题数据量较大，普通的求MST是会超时的。

d[i]=cost[i]-ans*dis[0][i]

据此二分。

但此题用Dinkelbach迭代更好

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; #define N 1010 double mp[N][N],c[N][N],x[N],y[N],z[N],e[N][N],d[N]; int vis[N],n; inline double prim(double mid) { double tmp,ans=0; for(int i=0;i
       
        z[j]?z[i]-z[j]:z[j]-z[i]; } le=0;ri=1001;//不开心。。这样才能水过 while(ri-le>1e-5) { mid=(le+ri)/2.0; // printf("prim:%lf\n",prim(0,mid)); if(prim(mid)>0) le=mid; else ri=mid; } printf("%.3f\n",mid); } return 0; }