社区讨论

求问,为啥开了30倍还是RE

P8191[USACO22FEB] Moo Network G参与者 4已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mlhzmmp4
此快照首次捕获于
2026/02/11 20:10
上周
此快照最后确认于
2026/02/11 20:55
上周
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e6+5;

int n,x,y,fa[maxn],fu,fv,u,v,tot,ans,m,w;

struct pos{
	int x,y;
};

pos a[maxn];

bool cmp(pos x,pos y){
	return x.x<y.x;
}

struct Edge{
	int u,v,w;
};

Edge edge[maxn];

bool cmp2(Edge x,Edge y){
	return x.w<y.w;
}

int find(int x){
	return (x==fa[x])?x:fa[x]=find(fa[x]);
}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		a[i]={x,y};
		fa[i]=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=min(j+10,n);j++){
			edge[++m]={i,j,(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)};
		}
	}
	sort(edge+1,edge+1+m,cmp2);
	for(int i=1;i<=m;i++){
		u=edge[i].u,v=edge[i].v,w=edge[i].w,fu=find(u),fv=find(v);
		if(fu!=fv){
			fa[fu]=fv;
			ans+=w;
			tot++;
			if(tot==n-1){
				cout<<ans;
				return 0;
			}
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e6+5;

int n,x,y,fa[maxn],fu,fv,u,v,tot,ans,m,w;

struct pos{
	int x,y;
};

pos a[maxn];

bool cmp(pos x,pos y){
	return x.x<y.x;
}

struct Edge{
	int u,v,w;
};

Edge edge[maxn];

bool cmp2(Edge x,Edge y){
	return x.w<y.w;
}

int find(int x){
	return (x==fa[x])?x:fa[x]=find(fa[x]);
}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		a[i]={x,y};
		fa[i]=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=min(j+10,n);j++){
			edge[++m]={i,j,(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)};
		}
	}
	sort(edge+1,edge+1+m,cmp2);
	for(int i=1;i<=m;i++){
		u=edge[i].u,v=edge[i].v,w=edge[i].w,fu=find(u),fv=find(v);
		if(fu!=fv){
			fa[fu]=fv;
			ans+=w;
			tot++;
			if(tot==n-1){
				cout<<ans;
				return 0;
			}
		}
	}
	return 0;
}

回复

8 条回复,欢迎继续交流。

正在加载回复...