求卡常
  • 板块灌水区
  • 楼主scyFBM
  • 当前回复12
  • 已保存回复12
  • 发布时间2023/5/31 20:46
  • 上次更新2023/10/23 14:13:08
查看原帖
求卡常
766405
scyFBM楼主2023/5/31 20:46

帮我康康这份代码还有什么可以优化的地方,不用管代码写的是什么。

#include<bits/stdc++.h>
using namespace std;
const int N=2009;
const int M=2000009;
int n,m,x[N],y[N],h[N];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct edge{
	int x,y;
	double w;
}e[M];
struct edge1{
	int x,y;
	double v,w;
}g[M];
inline bool cmp(const edge&a,const edge&b){
	return a.w<b.w;
}
int fa[N];
inline int find(int x){
	while(fa[x]!=x) x=fa[x]=fa[fa[x]];
    return x;
}
inline bool ok(double x){
	for(register int i=0;i<m;i++){
		e[i].x=g[i].x;
		e[i].y=g[i].y;
		e[i].w=g[i].v-x*g[i].w;
	}
	//kruskal
	for(register int i=0;i<n;i++) fa[i]=i;
	int cnt=0;
	double ans=0;
    sort(e,e+m,cmp);
    for(register int i=0;i<m;i++){
        int fx=find(e[i].x),fy=find(e[i].y);
        if(fx==fy) continue;
        fa[fx]=fy;
        ans+=e[i].w;
        if(++cnt==n-1) break;
    }
    return ans<=0;
}
int main(){
	n=read();
	for(register int i=0;i<n;i++) x[i]=read(),y[i]=read(),h[i]=read();
	for(register int i=0;i<n;i++){
		for(register int j=i+1;j<n;j++){
			g[m].x=i;
			g[m].y=j;
			g[m].v=fabs(h[i]-h[j]);
			g[m].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			m++;
		}
	}
	double l=0,r=10;
	while(r-l>0.00003){
		double mid=(l+r)/2;
		if(ok(mid)) r=mid;
		else l=mid;
	}
	cout<<fixed<<setprecision(3)<<l<<endl;
	return 0;
}

2023/5/31 20:46
加载中...