大概代码不规范,dalao顺便看一眼吧。。。。
查看原帖
大概代码不规范,dalao顺便看一眼吧。。。。
184271
l55584楼主2021/11/7 21:05

您看一遍代码可能就知道我那里写的不对了

#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运行错误。。。

是我哪里写的不规范吗

2021/11/7 21:05
加载中...