P1991无线通讯网 40分3个点MLE求助
查看原帖
P1991无线通讯网 40分3个点MLE求助
245089
i_am_a_joker楼主2022/6/8 13:49
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
	int u,v;double w; 
}e[550005];
int n,m,fa[550005];
void init(){for(int i=1; i<=1000000; i++) fa[i] = i;}
int getfa(int x)
{
	if(x == fa[x]) return fa[x];
	fa[x] = getfa(x);
	return fa[x];
}
bool merge(int x,int y)
{
	if(getfa(x) == getfa(y)) return false;
	int grx = getfa(x),gry = getfa(y);
	fa[grx] = gry;
	return true;
}
double dis(int x1,int y1,int x2,int y2)
{
	return sqrt((x1-y1)*(x1-y1) + (x2-y2)*(x2-y2));
}
bool cmp(Edge x,Edge y)
{
	return x.w < y.w;
}
double ans;
int tx[550005],ty[550005];
int main()
{
	cin>>n>>m;
	init();
	int an = m-n;
	int cnt = 0;
	for(int i=1; i<=m; i++)
	{
		cin>>tx[i]>>ty[i];
		cnt++;
		for(int j=1; j<i; j++)
		{
			e[cnt].u = i,e[cnt].v = j;
			e[cnt].w = dis(tx[i],tx[j],ty[i],ty[j]);
		}
	}
	sort(e+1,e+m+1,cmp);
	int cnt1 = 0;
	for(int i=1; i<=cnt; i++)
	{
		int x = e[i].u, y = e[i].v;
		if(merge(x,y))
		{
			ans = e[i].w;
			cnt1++;
			if(cnt1 >= an){printf("%.2lf",ans); break;}
		}
		//if(cnt1 == an-1) break;
	}
	return 0;
}
2022/6/8 13:49
加载中...