G - Arctic Network

G - Arctic Network

#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define MAXN 510using namespace std;double an;int fa[MAXN];int t,n,m,tot,sum;double x[MAXN],y[MAXN],ans[MAXN];struct nond{ ???int x,y;double z;}v[MAXN*MAXN];int cmp(nond a,nond b){ ???return a.z<b.z;}int find(int x){ ???if(fa[x]==x) ???return x; ???else ?return fa[x]=find(fa[x]);}int main(){ ???scanf("%d",&t); ???while(t--){ ???????an=0;sum=0;tot=0; ???????scanf("%d%d",&n,&m); ???????for(int i=1;i<=m;i++) ???????????scanf("%lf%lf",&x[i],&y[i]); ???????for(int i=1;i<=m;i++) ???????????for(int j=i+1;j<=m;j++){ ???????????????double tmp=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); ???????????????v[++tot].x=i;v[tot].y=j;v[tot].z=tmp; ???????????} ???????for(int i=1;i<=m;i++) ???fa[i]=i; ???????sort(v+1,v+1+tot,cmp); ???????for(int i=1;i<=tot;i++){ ???????????int dx=find(v[i].x); ???????????int dy=find(v[i].y); ???????????if(dx==dy) ???continue; ???????????fa[dy]=dx; ???????????ans[++sum]=v[i].z; ???????????if(sum==m-1) ???break; ???????} ???????for(int i=1;i<=m-n;i++) ???????????an=max(an,ans[i]); ???????printf("%.2lf\n",an); ???}}