不明白为什么会爆0
查看原帖
不明白为什么会爆0
307826
Lamorak楼主2021/2/1 13:19
#include<bits/stdc++.h>
using namespace std;
const int N=1e6,M=1e6;
int n,m,head[N],k,tot,pre[N],x[N],y[N];
struct node{
	int u,v;
	double w;
}a[M];
double dis(int i,int j){
	return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
}
void add(int u,int v,double w){
	a[++tot].u=u;
	a[tot].v=v;
	a[tot].w=w;
}
bool cmp(node d1,node d2){
	return d1.w<d2.w;
}
int find(int x){
	if(pre[x]=x) return x;
	else return pre[x]=find(pre[x]);
}
int main(){
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<m;i++){
		for(int j=i+1;j<=m;j++){
			add(i,j,dis(i,j));
		}
	}
	for(int i=1;i<=n;i++) pre[i]=i;
	sort(a+1,a+tot+1,cmp);
	for(int i=1;i<=tot;i++){
		int rx=find(a[i].u);
		int ry=find(a[i].v);
		if(rx!=ry){
			pre[rx]=ry;
			k++;
			if(k>=m-n){
				printf("%.2llf",a[i].w);
				return 0;
			}
		}
	}
	return 0;
}


2021/2/1 13:19
加载中...