/*关于最小生成树的等效边,就是讲两个相同的集合连接在一起 先建立一个任意最小生成树,这条边分开的两个子树的节点最大的一个和为A,sum为最小生成树的权值和,B为sum-当前边的权值 不断枚举最小生成树中的边找最优值即可。 */ #include<stdio.h> #include<string.h> #include<math.h> #include<stdlib.h> #define N 1100 struct nodee { int u,v; double w; } edge[N*N]; struct node { int u,v,next; double w; } bian[N*N]; int index,yong,head[N],visit[N],n,pre[N],flag[N],c[N],aa[N],bb[N]; double ans; double sum; void init() { index=0; yong=0; sum=0; int i; for(i=1; i<=n; i++) pre[i]=i; memset(head,-1,sizeof(head)); memset(flag,0,sizeof(flag)); } int cmp(const void *a,const void *b) { return (*(struct nodee *)a).w>(*(struct nodee *)b).w?1:-1; } double distance(int u,int v) { return sqrt(1.0*(aa[u]-aa[v])*(aa[u]-aa[v])+(bb[u]-bb[v])*(bb[u]-bb[v])*1.0); } int find(int x) { if(pre[x]!=x) pre[x]=find(pre[x]); return pre[x]; } void addedge(int u,int v,double w) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].next=head[u]; head[u]=yong++; } void creat() { int k=0,i; for(i=0; i<index&&k<n-1; i++) { int u=find(edge[i].u); int v=find(edge[i].v); if(u!=v) { k++; flag[k]=i; sum=sum+edge[i].w; addedge(edge[i].u,edge[i].v,edge[i].w); addedge(edge[i].v,edge[i].u,edge[i].w); pre[u]=v; } } return ; } void dfs(int u)//定义全局变量好点 { int i; visit[u]=1; for(i=head[u]; i!=-1; i=bian[i].next) { int v=bian[i].v; if(!visit[v]) { dfs(v); } } if(ans<c[u]) ans=c[u]; } int main() { int t,i,j; double m; scanf("%d",&t); while(t--) { scanf("%d",&n); init(); for(i=1; i<=n; i++) scanf("%d%d%d",&aa[i],&bb[i],&c[i]); for(i=1; i<n; i++) for(j=i+1; j<=n; j++) { edge[index].u=i; edge[index].v=j; edge[index++].w=distance(i,j); } qsort(edge,index,sizeof(edge[0]),cmp); creat(); m=-1; for(i=1; i<n; i++) { int e=flag[i]; memset(visit,0,sizeof(visit)); visit[edge[e].u]=1; ans=0; dfs(edge[e].v); max1=ans; memset(visit,0,sizeof(visit)); visit[edge[e].v]=1; ans=0; dfs(edge[e].u); max2=ans; if(m<1.0*(max1+max2)/(sum-edge[e].w)) m=1.0*(max1+max2)/(sum-edge[e].w); } printf("%.2f ",m); } return 0; }