本地运行不了,为啥洛谷能AC
查看原帖
本地运行不了,为啥洛谷能AC
524782
2_6HogCycle楼主2021/11/18 18:09
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,f[20080000],sum,cnt;
int dis;
int k,pointx[20080000],pointy[20080000];
struct edge
{
	int r;
	int v;
	int weight;
 };
int findf(int v)
{
	if(f[v]==v)return v;
	else{
		f[v]=findf(f[v]);
		return f[v];
	}
}
bool merge1(int a,int b){
	int t1=findf(a);
	int t2=findf(b);
	if(t1!=t2)
	{
		f[t2]=t1;
		return true;
	}
	else return false;
}
bool cmp(struct edge x,struct edge y){
	return x.weight<y.weight;
}
int main()
{
	struct edge e[20080305];
	cin>>n>>m;
	k=1;
	for(int i=1;i<=n;i++)f[i]=i;	
	for(int i=1;i<=n;i++)
	{	
		cin>>pointx[i]>>pointy[i];
		for(int j=1;j<i;j++)
		{
			dis=(pointx[i]-pointx[j])*(pointx[i]-pointx[j])+(pointy[i]-pointy[j])*(pointy[i]-pointy[j]);
			if(dis>=m)
			{
				e[k].v=i;
				e[k].r=j;
				e[k].weight=dis;
				k++;
			}
		}	
	}	
	sort(e+1,e+1+k,cmp);
	for(int i=1;i<=k;i++){
		if(merge1(e[i].v,e[i].r)){
            cnt++;
            sum+=e[i].weight;
		}
		if(cnt==n-1)
		{
			cout<<sum;
            return 0;
		}			
	}
	cout<<-1;
	return 0;
}
2021/11/18 18:09
加载中...