link
题目大意
有$n$个点的完全图，每条边有价值$c$与权值$w$，求$\frac{\sum c}{\sum r}$最小
试题分析
一道分数规划，我们二分$k$值，判断当每条边边权为$c-k\times w$时的最小生成树是否大于$0$，然后就会$T$掉，需要卡常，好像说正解是牛顿迭代法。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<climits> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int N=1000001;const int M=1000001; struct node{ int u,v; double c,w; }x[N]; struct Node{ int u,v;double w; }s[N]; double l,r,eps=1e-4; int xx[N],yy[N],h[N],cnt,f[N],n; bool cmp(Node x1,Node x2){return x1.w<x2.w;} int find(int x){if(f[x]==x) return x;return f[x]=find(f[x]);} double dis(int x1,int y1,int x2,int y2){return (double)sqrt((double)(x1-x2)*(x1-x2)*1.0+(double)(y1-y2)*(y1-y2)*1.0);} bool check(double k){ for(int i=1;i<=cnt;i++) s[i].u=x[i].u,s[i].v=x[i].v,s[i].w=x[i].c-k*x[i].w; for(int i=1;i<=n;i++) f[i]=i; sort(s+1,s+cnt+1,cmp); double ans=0; for(int i=1;i<=cnt;i++){ int t1=find(s[i].u),t2=find(s[i].v); if(t1!=t2){ ans+=s[i].w; f[t2]=t1; } }return ans>=0; } double maxn=-INT_MAX; signed main(){ // freopen("3.in","r",stdin); while(1){ n=read(); maxn=-INT_MAX,cnt=0; if(!n) return 0; for(int i=1;i<=n;i++) xx[i]=read(),yy[i]=read(),h[i]=read(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) x[++cnt].u=i,x[cnt].v=j,x[cnt].w=dis(xx[i],yy[i],xx[j],yy[j]),x[cnt].c=abs(h[i]-h[j]); l=0,r=101; while(l<=r){ double mid=(l+r)/2; if(check(mid)) maxn=max(maxn,mid),l=mid+eps; else r=mid-eps; } printf("%.3lf\n",maxn); } }