关于kruskal,它活了
查看原帖
关于kruskal,它活了
432183
JoeBiden2020楼主2021/12/15 13:20
#include<bits/stdc++.h>
using namespace std;
int n,m=0,x[5001],y[5001],fa[5001];
struct ccf{
	int from,to;
	double val;
}e[8500001];
int fuck(int k){
	if(fa[k]==k)return k;
	else return fa[k]=fuck(fa[k]);
}
bool cmp(ccf nt,ccf sb){
	return nt.val<sb.val;
}
double getdis(int p1,int p2){
	return (double)sqrt((double)pow((double)x[p1]-(double)x[p2],2)+pow((double)y[p1]-(double)y[p2],2));
}
void addedge(int u,int v){
	double temp=getdis(u,v);
	if(temp>1e6)return;
	e[++m].from=u;
	e[m].to=v;
	e[m].val=temp;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(register int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		fa[i]=i;
	}
	for(register int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			addedge(i,j);
		}
	}
	sort(e+1,e+m+1,cmp);
	double ans=0.0;
	for(register int i=1;i<=m;i++){
		int t1=fuck(e[i].from),t2=fuck(e[i].to);
		if(t1==t2)continue;
		ans+=e[i].val;
		fa[t1]=t2;
	}
	cout<<fixed<<setprecision(2)<<ans;
}
2021/12/15 13:20
加载中...