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

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

据此二分。

但此题用Dinkelbach迭代更好

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 1010double 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;}