还比较好做的题，直接01分数规划二分答案即可，n小完全图用prim
然而
cnmd
double不可以用memset初始化我透
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include <algorithm> 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]<d[x]))x=j; if(!x)break; v[x]=1; ans+=d[x]; for(int y=1;y<=n;y++) d[y]=min(d[y],a[x][y]); } if(ans>=0)l=mid; else r=mid; } printf("%.3f ",l); } return 0; }