刷题记录表

#include<bits/stdc++.h>
using namespace std;
inline int read(int &a){a=0;int f=1;char c=getchar();if(c==EOF) return a=EOF;
for(;c<'0' || c>'9';c=getchar()){if(c=='-') f=-1;if(c==EOF) return a=EOF;}
for(;c<='9' && c>='0';a=a*10+c-'0',c=getchar());return a*=f;}
int n;
struct shop{
	int x,y,P;
} a[1010];
struct road{
	int a,b;
	double v;
} b[1000010];
int tot;
bool sort1(road a,road b){return a.v<b.v;}
struct tree{
	int next,ver;
	double val;
} e[2010];
int head[1010],cnt;
void add(int a,int b,double v)
{
	e[++cnt].next=head[a],
	head[a]=cnt,
	e[cnt].ver=b,
	e[cnt].val=v;
	e[++cnt].next=head[b],
	head[b]=cnt,
	e[cnt].ver=a,
	e[cnt].val=v;
}
int fa[1010];
double f[1010][1010];
double ans,sum;

int reg(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=reg(fa[x]);
}

void dfs(int x,int l,int rt,double mx)
{
	for(int i=head[x];i;i=e[i].next)
	if(e[i].ver!=l)
	{
		f[rt][e[i].ver]=max(mx,e[i].val);
		dfs(e[i].ver,x,rt,max(mx,e[i].val));
	}
}

int main()
{
	read(n);
	for(int i=1;i<=n;i++)
	read(a[i].x),read(a[i].y),read(a[i].P),fa[i]=i;
	for(int i=1;i<n;i++)
	for(int j=i+1;j<=n;j++)
	b[++tot].a=i,b[tot].b=j,
	b[tot].v=sqrt(1.0*(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
	sort(b+1,b+1+tot,sort1);
	for(int i=1,j=1;i<=tot && j<n;i++)
	if(reg(b[i].a)!=reg(b[i].b))
	{
		fa[reg(b[i].a)]=reg(b[i].b);
		add(b[i].a,b[i].b,b[i].v);
		sum+=b[i].v,j++;
	}
	for(int i=1;i<=n;i++) dfs(i,i,i,0);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	ans=max(ans,1.0*(a[i].P+a[j].P)/(sum-f[i][j]));
	printf("%.2lf\n",ans);
	return 0;
}