萌新求条,玄关
查看原帖
萌新求条,玄关
681941
OIer_Hhy楼主2024/8/8 09:44
#include<bits/stdc++.h>
using namespace std; 
const int N=1e3+10,M=1e6+100;
int n,m;
struct city{
	int x,y,p;
}a[N];
struct edge{
	int u,v;
	double w;
}e[M];
int fa[N];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
vector<edge> v;
bool cmp(edge x,edge y){
	return (a[x.u].p+a[x.v].p)/x.w>(a[y.u].p+a[y.v].p)/y.w;
}
double kruskal(){
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+m+1,cmp); 
	double ans=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		int fx=find(e[i].u),fy=find(e[i].v);
		if(fx==fy) continue;
		fa[fx]=fy;
		v.push_back(e[i]);
		ans+=e[i].w;
		cnt++;
		if(cnt==n-1)  return ans;
	}
}
double dist(double x1,double y1,double x2,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void solve(){
	v.clear();
	memset(a,0,sizeof a);
	memset(e,0,sizeof e);
	m=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].p;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			double w=dist(a[i].x,a[i].y,a[j].x,a[j].y); 
			e[++m]={i,j,w};
		}
	}
	double res=kruskal(),ans=0;
	for(auto x:v){
		ans=max(ans,(a[x.u].p+a[x.v].p)/(res-x.w));
	}	
	printf("%.2lf\n",ans);
} 
int main(){
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}
2024/8/8 09:44
加载中...