社区讨论

求助,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 条回复,欢迎继续交流。

正在加载回复...