@[Hiraeth](/space/show?uid=99460) 您的并查集写得蒟蒻看不懂，没有递归吧（orz
by runtime_error @ 2019-01-04 00:19:41
我和你写的基本一样，也是40分
```cpp
#include<cmath>
#include<cstdio>
#include<algorithm>
#define N 10001
#define M 10000001
using namespace std;
struct edge{
int u,v;
double w;
} e[M];
int i,j,m,n,f1,f2,fa[N];
double x[N],y[N];
int tot=0,sum=0,ans=0;
bool cmp(edge aa,edge bb)
{return aa.w<bb.w;}
inline double dist(int i,int j)
{return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}
inline int find(int x)
{return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{//freopen("wjf.in","r",stdin);
scanf("%d%d",&m,&n);
printf("%d\n",n);
for(i=1;i<=n;i++)
{
fa[i]=i;
scanf("%lf%lf",&x[i],&y[i]);
}
for(i=2;i<=n;i++)
for(j=1;j<i;j++)
{
e[++tot].w=dist(i,j);
e[tot].u=i;e[tot].v=j;
}
sort(e+1,e+2*tot+1,cmp);
for(i=1;i<=2*tot;i++)
{
f1=find(e[i].u);f2=find(e[i].v);
if(f1==f2) continue;
sum++;
if(sum==n-m) break;
}
printf("%.2f",e[i].w);
return 0;
}
```
by Luminescent_Apophis @ 2019-05-06 21:05:20
#include<bits/stdc++.h>
using namespace std;
int s,p,tot,num;
double ans;
struct node
{ int x,y;
}a[510];
double dis(node x,node y)
{ return sqrt(pow(x.x-y.x,2)+pow(x.y-y.y,2));
}
struct edg
{ int to,nex;
double v;
}e[1000100];
bool cmp(edg x,edg y)
{ return x.v<y.v;
}
int fa[510];
int find(int x)
{ if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void kru()
{ for(int i=1;i<=tot;i++)
{ int u=find(e[i].nex);
int v=find(e[i].to);
if(u==v) continue;
fa[u]=v; num++;
if(num==p-s)
{ ans=e[num].v;
break;
}
}
}
int main()
{ cin>>s>>p;
for(int i=1;i<=p;i++)
cin>>a[i].x>>a[i].y;
for(int i=1;i<=p;i++)
fa[i]=i;
for(int i=1;i<=p;i++)
for(int j=i+1;j<=p;j++)
{ e[++tot].to=j;
e[tot].nex=i;
e[tot].v=dis(a[i],a[j]);
}
sort(e+1,e+1+tot,cmp);
kru();
printf("%.2lf",ans);
return 0;
}
为什么我也是40分
by 丶雖 @ 2019-05-19 10:36:25
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10000;
int cnt;
double S,P,x[N],y[N],fa[N],ans,mst;
struct Mo
{
double from,to,w;
bool operator<(Mo a)const{return w<a.w;}
}Ha[N];
int find(int t)
{
return fa[t]=(fa[t]==t?t:find(fa[t]));
}
int main()
{
cin>>S>>P;
for(int i=1;i<=P;i++)
{
cin>>x[i]>>y[i];
for(int j=1;j<i;j++)
{
Ha[++cnt].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
Ha[cnt].from=i,Ha[cnt].to=j;
}
}sort(Ha+1,Ha+1+cnt);
for(int i=1;i<=P;i++)
fa[i]=i;
for(int i=1;i<=cnt;i++)
{
int X=Ha[i].from,Y=Ha[i].to;
if(find(X)==find(Y))continue;
ans=Ha[i].w;
fa[X]=Y;
mst++;
if(mst>=P-S)
break;
}
printf("%.2lf",ans);
}
```
40分
by cqsbz_cxy @ 2019-08-24 11:12:52