Kruskal 30分,样例2没过,求调!
查看原帖
Kruskal 30分,样例2没过,求调!
1015977
heyZZZ楼主2024/7/2 16:43
#include<bits/stdc++.h>
using namespace std;
#define oo INT_MAX
//#define int long long
int n,m,f[1005],x[1005],y[1005],tot;
struct stu{int u,v,w;}a[1000005];
bool cmp(stu a,stu b){return a.w<b.w;}
int fd(int x){
	if(x==f[x]) return x;
	return f[x]=fd(f[x]);
}
void kruskal(){
	for(int i=1;i<=n;i++) f[i]=i;
	sort(a+1,a+tot+1,cmp);
	int k=n-m+1;
	for(int i=1;i<=tot;i++){
		if(fd(a[i].u)!=fd(a[i].v)) f[fd(a[i].u)]=f[fd(a[i].v)],k--;
		if(k==m){
			printf("%.2lf\n",sqrt(a[i].w));
			return;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		for(int j=1;j<i;j++){
			a[++tot]={i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])};
		}
	}
	kruskal();
}
2024/7/2 16:43
加载中...