社区讨论

40分,最后3个点RE???

P1991无线通讯网参与者 4已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lod7vvbg
此快照首次捕获于
2023/10/31 02:12
2 年前
此快照最后确认于
2023/11/05 12:38
2 年前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,fa[10005],k=0,sq1[10005],sq2[10005];double ans=0,s;
int find(int x){
	int cc;
	do{
		cc=fa[x];
		if(fa[x]!=x)
	    fa[x]=find(fa[x]);
}while(cc!=fa[x]);
	return fa[x];
}
struct stu{
	int a,b;double c;
}st[10005];
bool cmp(stu x,stu y){
	return x.c<y.c;
}
void krus(){
	for(int i=1;i<=n;i++){
		//cout<<st[i].a<<' '<<st[i].b<<' '<<st[i].c<<endl;
		if(k==n-s)break;
		if(find(st[i].a)!=find(st[i].b)){
			//cout<<"QQQ"; 
			fa[find(st[i].a)]=find(st[i].b);
			ans+=st[i].c;
			k++;
		}
	}
}
int main(){
	cin>>s>>n;
	m=1;
	for(int i=1;i<=n;i++){
	    int xx,yy;
		cin>>xx>>yy;
		sq1[i]=xx;sq2[i]=yy;
		for(int j=1;j<i;j++){
			if(i!=j){
				st[m].a=j;
				st[m].b=i;
				st[m].c=sqrt((sq1[i]-sq1[j])*(sq1[i]-sq1[j])+(sq2[i]-sq2[j])*(sq2[i]-sq2[j]));
				m++;
			}
		}	
	}
	for(int i=1;i<=n;i++)
	fa[i]=i;
	sort(st,st+m,cmp);
	krus();
	//cout<<k<<endl;
	printf("%.2lf",st[k].c);
	return 0;
} 

回复

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

正在加载回复...