社区讨论
求助,WA:7~10
P2872[USACO07DEC] Building Roads S参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi8kom13
- 此快照首次捕获于
- 2025/11/21 16:02 4 个月前
- 此快照最后确认于
- 2025/11/21 17:40 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,x[1005],y[1005];
int f[1005],cnt=0,X,Y;
double tot=0,temp1,temp2;
struct node{
int u,v;
double w;
}e[500005];
int fin(int n){
if(f[n]==n) return n;
return f[n]=fin(f[n]);
}
void he(int xx,int yy){
int t1=fin(xx),t2=fin(yy);
if(t1!=t2) f[t1]=t2;
}
bool cmp(const node t1,const node t2){
return t1.w<t2.w;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
temp1=double((x[i]-x[j])*(x[i]-x[j]));
temp2=double((y[i]-y[j])*(y[i]-y[j]));
cnt++;
e[cnt].u=i;
e[cnt].v=j;
e[cnt].w=sqrt(temp1+temp2);
// cout<<e[cnt].w<<'\n';
}
}
for(int i=1;i<=m;i++){
cin>>a>>b;
cnt++;
e[cnt].u=a;
e[cnt].v=b;
e[cnt].w=0.0;
}
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;i++){
X=fin(e[i].u),Y=fin(e[i].v);
if(X!=Y){
he(X,Y);
tot+=e[i].w;
// cout<<"tot="<<tot<<'\n';
}
}
printf("%.2lf\n",tot);
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...