代码40求助
查看原帖
代码40求助
711159
qb1_1楼主2023/8/13 11:26
#include<bits/stdc++.h>
using namespace std;
int qb[20000001];
int n,m;
double ans,a[10000001],b[10000001];
int k,z;
struct wsqb{
	int u,v;
	double w;
}edge[200001];
bool cmp(wsqb a,wsqb b){
	return a.w<b.w;
}
int get(int x){
	if(x==qb[x]) return x;
	return qb[x]=get(qb[x]);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
		for(int j=1;j<i;j++){
			k++;
			edge[k].u=i;
			edge[k].v=j;
			edge[k].w=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
		}
	}	
	sort(edge+1,edge+k+1,cmp);
	for(int i=1;i<=m;i++)
		qb[i]=i; 
	for(int i=1;i<=k;i++){
		int v=get(edge[i].v);
		int u=get(edge[i].u);
	    if(u!=v)	    	    
		qb[v]=u;
		ans=edge[i].w;
		z++;
		if(z>=m-n){
		printf("%.2lf",ans);
		return 0;	
		}
	}
}
2023/8/13 11:26
加载中...