50分kruskal求助
查看原帖
50分kruskal求助
393674
jixiang楼主2021/7/24 09:47
#include<bits/stdc++.h>
using namespace std;
const int M=10009;
int n,m,k,cnt;
int fa[M];
int x[M],y[M];

/*double dis(int a,int b)
{
	double xx=(x[a]-x[b])*(x[a]-x[b]);
	double yy=(y[a]-y[b])*(y[a]-y[b]);
	return sqrt(xx+yy);
//	a[cnt].val=(double)sqrt((double)(xx[i]-xx[j])*(xx[i]-xx[j])+(double)(yy[i]-yy[j])*(yy[i]-yy[j]));
	
}*/

struct edge {
	int f,t;
	double w;
	void input(int xx,int yy)
	{
		f=xx;t=yy;
		w=(double)sqrt((double)(x[f]-x[t])*(x[f]-x[t])+(double)(y[f]-y[t])*(y[f]-y[t]));
    } 
}a[1000009];


bool cmp(edge x,edge y){
	return x.w<y.w;
}

int getfa(int x)
{
	if(fa[x]!=x)return fa[x]=getfa(fa[x]);
	else return x;
}

int main()
{
	cin>>n>>m;
	int aa,bb;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		scanf("%d%d",&x[i],&y[i]);
	}
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&aa,&bb);
		if(getfa(aa)!=getfa(bb))fa[aa]=bb;
	}
	
	m=0;
	
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(getfa(i)!=getfa(j))a[++m].input(i,j);
	
	sort(a+1,a+1+m,cmp);
	
	double  ans=0;
	for(int i=1;i<=m;i++)
	{
		int z=a[i].f;
		double  v=a[i].w;
		int c=a[i].t;
		
		int a=getfa(z);
		int b=getfa(c);
		if(a!=b)fa[a]=b,ans+=v;
	}
	
	printf("%.2lf",ans);
	
	//for(int j=1;j<=m;j++)cout<<a[j].f<<" t o "<<a[j].t<<"is "<<a[j].w<<endl;
	
}
2021/7/24 09:47
加载中...