WA20pts Kruskal 求调
查看原帖
WA20pts Kruskal 求调
1475943
libu2333楼主2025/7/1 17:51

如题,调了两个小时了,球球路过的谷友帮帮忙吧 qwq。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1005;
const int MAXM=500005;
int n,k;
int f[MAXN],x[MAXN],y[MAXN];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
struct edge{int u,v;int w;} e[MAXM];
bool cmp(edge a,edge b){return a.w<b.w;}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
	int m=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<n;j++){
			int dx=x[i]-x[j],dy=y[i]-y[j];
			int d=dx*dx+dy*dy;
			e[++m].u=i;e[m].v=j,e[m].w=d;
		}
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++)f[i]=i;
	int cnt=n,i=1;
	for(i;i<=m&&cnt>k;i++){
        int u=find(e[i].u),v=find(e[i].v);
		if(u!=v) f[u]=v,cnt--;
	}
	double ans=0.0;
	for(i;i<=m;i++){
        int u=find(e[i].u),v=find(e[i].v);
		if(u!=v){
			ans=sqrt((double)e[i].w);
			cout<<fixed<<setprecision(2)<<ans<<endl;
			return 0;
		}
	}
}
2025/7/1 17:51
加载中...