Kruscal爆0求助
查看原帖
Kruscal爆0求助
784202
MarshmallowDream楼主2023/12/17 15:27
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int parent[1005],m,n,a[505];
struct edge
{
	int u,v,w;
}edges[1005];
bool cmp(edge a,edge b)
{
	return a.w>b.w;
}
void init()
{
	memset(parent,-1,sizeof(parent));
}
int find(int x)
{
	int s;
	for(s=x;parent[s]>0;s=parent[s]);
	while(s!=x)
	{
		int tmp=parent[x];
		parent[x]=s;
		x=tmp;
	}
	return s;
}
void union_tree(int tree1,int tree2)
{
	int treef=find(tree1),trees=find(tree2);
	int tmp=parent[treef]+parent[trees];
	if(parent[treef]>parent[trees])
	{
		parent[treef]=trees;
		parent[trees]=tmp;
	}
	else
	{
		parent[trees]=treef;
		parent[treef]=tmp;
	}
}
int Kruscal()
{
	int sumweight=0;
	int u,v,num;
	init();
	for(int i=1;i<=n;i++)
	{
		u=edges[i].u;
		v=edges[i].v;
		edges[i].w=sqrt(u*u+v*v);
		if(find(u)!=find(v))
		{
			sumweight+=edges[i].w;
			num++;
			union_tree(u,v);
		}
	}
	return num;
}
int main()
{
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		edges[i].u=x;
		edges[i].v=y;
	}
	printf("%d\n",Kruscal());
	return 0;
}
2023/12/17 15:27
加载中...