社区讨论
求问,为啥开了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 条回复,欢迎继续交流。
正在加载回复...