40的痛
查看原帖
40的痛
596407
ok_one楼主2022/3/31 21:14
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e7+5;

int n,m;

int pp[N],a[N],b[N];

void intin()
{
	for(int i=1;i<=m;i++)
	{
		pp[i]=i;
	}
}

int find(int x)
{
	while(x!=pp[x]) pp[x]=x;
	return x;
}
struct node{
	int u,v;
	double w;
	bool operator<(const node & a) const {
		return w<a.w;
	}
};

vector <node> q;

int kruskal()
{
	double ans=0;
	int cnt=0;
	for(int i=0;i<q.size();i++)
	{
		int v=q[i].v;
		int u=q[i].u;
		double w=q[i].w;
		if(find(u)!=find(v))
		{
			cnt++;
			pp[find(v)]=find(u);
			ans=w;
		}
		if(cnt>=m-n) 
		{
			printf("%.2lf\n",ans);
			break;
		}
	}
	
}
int main()
{
	cin>>n>>m;
	intin();
	for(int i=1;i<=m;i++)
	{
		double w;
		cin>>a[i]>>b[i];
		for(int j=1;j<i;j++)
		{
		w=sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
		q.push_back({i,j,w});
		}
	}
	sort(q.begin(),q.end());
	kruskal();
	return 0;
}
2022/3/31 21:14
加载中...