还比较好做的题，直接01分数规划二分答案即可，n小完全图用prim

然而

cnmd

double不可以用memset初始化我透

#include
     
      #include
      
       #include
       
        #include
        
         #include 
         
          using namespace std;const int N=1007;const double eps=1e-6;struct city{    int x,y,v;}c[N];double rr[N][N],cost[N][N],a[N][N],mid,d[N],ans,l,r;int n;bool v[N];double len(int x,int y){    return sqrt((c[x].x-c[y].x)*(c[x].x-c[y].x)+(c[x].y-c[y].y)*(c[x].y-c[y].y));}int main(){    //freopen("in","r",stdin);    //freopen("out.out","w",stdout);    while(1){        double num=0.0;        scanf("%d",&n);        if(n==0)break;        for(int i=1;i<=n;i++){            scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].v);        }        for(int i=1;i<=n;i++)            for(int j=i;j<=n;j++){                rr[j][i]=rr[i][j]=len(i,j);                num+=(cost[i][j]=cost[j][i]=abs(c[i].v-c[j].v));            }        l=0.0,r=100;        while(l+eps<=r){            mid=(l+r)/2;            ans=0;            for(int i=1;i<=n;i++)                for(int j=i;j<=n;j++){                    if(i==j)a[i][j]=0x3f3f3f3f;                    else a[i][j]=a[j][i]=cost[i][j]-mid*rr[i][j];                }            for (int i = 1; i <= n; i++) d[i] =0x3f3f3f3f;                memset(v,0,sizeof(v));                d[1]=0;                while(1){                    int x=0;                    for(int j=1;j<=n;j++)                        if(!v[j]&&(x==0||d[j]
          
           =0)l=mid; else r=mid; } printf("%.3f\n",l); } return 0;}