思路：直接先求一下最小生成树，然后用树形dp来求最优值。也就是两遍dfs。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #define Maxn 2010 using namespace std; struct Edge{ int u,v; double c; int operator <(const Edge &temp) const { return c<temp.c; } }p[1000010]; struct PP{ int u,v,next; double val; }edge[Maxn*2]; struct Point{ double x,y; }city[Maxn]; int set[Maxn],e,vi[10010],num[Maxn],head[Maxn],road[Maxn],Max[Maxn],lMax[Maxn]; double ans,S; int find(int x) { if(x!=set[x]) set[x]=find(set[x]); return set[x]; } int merg(int a,int b) { int x,y; x=find(a); y=find(b); if(x==y) return 0; set[x]=y; return 1; } void add(int u,int v,double val) { edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++; edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++; memset(Max,0,sizeof(Max)); } double DIS(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void init() { for(int i=0;i<Maxn;i++) set[i]=i,num[i]=0; memset(head,-1,sizeof(head)); memset(vi,0,sizeof(vi)); memset(road,0,sizeof(road)); e=0; } void dfs(int u) { int i,v; vi[u]=1; Max[u]=lMax[u]=num[u]; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v; if(vi[v]) continue; dfs(v); if(Max[v]>Max[u]){ lMax[u]=Max[u]; Max[u]=Max[v]; road[u]=v; } else if(Max[v]>lMax[u]){ lMax[u]=Max[v]; } } } void predfs(int u,int sum) { int i,v; vi[u]=1; double a,b; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v; if(vi[v]) continue; if(road[u]==v) a=max(lMax[u],sum); else a=max(sum,Max[u]); a+=Max[v]; b=S-edge[i].val; if(a/b>ans){ ans=a/b; } if(road[u]==v) predfs(v,max(lMax[u],sum)); else predfs(v,max(Max[u],sum)); } } int main() { int t,n,m,i,j,x,y,c; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%lf%lf%d",&city[i].x,&city[i].y,&num[i]); int cnt=0; for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ p[++cnt].u=i,p[cnt].v=j,p[cnt].c=DIS(city[i],city[j]); } } sort(p+1,p+1+cnt); int cc=0; double temp=0; int lis[Maxn]; for(i=1;i<=cnt;i++){ if(merg(p[i].u,p[i].v)){ temp+=p[i].c; lis[++cc]=i; } if(cc==n-1) break; } for(i=1;i<=cc;i++){ add(p[lis[i]].u,p[lis[i]].v,p[lis[i]].c); } S=temp; ans=0; dfs(1); memset(vi,0,sizeof(vi)); predfs(1,0); printf("%.2lf ",ans); } return 0; }