您看一遍代码可能就知道我那里写的不对了
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int x[N],y[N];
int n,s;
const double eps=1e-6;
struct edge
{
int u,v;
double rul;
bool operator <(const edge a)const
{
return rul<a.rul;
}
};
set<edge> e;
struct sett
{
int fa[N];
void clear()
{
for(int i=1;i<=n;i++) fa[i]=i;
}
void con(int a,int b)
{
int top;
while(fa[a]!=a) a=fa[a]=fa[fa[a]];
fa[top]=b;
}
bool query(int a,int b)
{
while(fa[a]!=a) a=fa[a]=fa[fa[a]];
while(fa[b]!=b) b=fa[b]=fa[fa[b]];
return a==b;
}
}S;
bool Kruskal(double D)
{
S.clear();
int sum=n;
for(set<edge>::iterator it=e.begin();it!=e.end()&&sum>s+1;it++)
{
edge to=*it;
if(to.rul>=D+eps) break;
if(S.query(to.u,to.v)) continue;
S.con(to.u,to.v);sum--;
}
return sum<=s+1;
}
int main()
{
// freopen("wireless.in","r",stdin);
//freopen("wireless.out","w",stdout);
cin>>s>>n;s--;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
edge t;
double l=eps,r=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
t.rul=sqrt(abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]));
t.u=i;t.v=j;
e.insert(t);
r=max(r,t.rul);
}
while(l<r)
{
double mid=(l+r)/2.0;
if(Kruskal(mid)) r=mid;
else l=mid+eps;
}
printf("%.2f",l);
return 0;
}
不加文件输入输出全RE,加了又全WA
第一组数据本地过了洛谷IDE运行错误。。。
是我哪里写的不规范吗