刚学OI,萌新求查错
查看原帖
刚学OI,萌新求查错
278259
RemiliaScar1et楼主2020/6/3 15:50

想用KruskalKruskal

但是不知道错在哪里

#include <bits/stdc++.h>
using namespace std;
const int EDG=1000010;
int parent[EDG];
void init();
int find(int x);
int union_(int x,int y);
int search_(int x,int y);
int n,m;
struct edg
{
	int st,ed;
	double we;
} arc[EDG];
int tot=0;
void add(int x,int y,double z)
{
	arc[++tot].we=z;
	arc[tot].st=x;
	arc[tot].ed=y;
}
struct node
{
	double x,y;
} ver[EDG];
bool cmp(edg a,edg b)
{
	return a.we<b.we;
}
double distance(int x1,int x2,int y1,int y2)
{
	double tmp=(double)sqrt((double)(x2-x1)*(double)(x2-x1)+(double)(y2-y2)*(double)(y2-y1));
	return tmp;
}


int main()
{
	init();
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>ver[i].x>>ver[i].y;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			add(i,j,distance(ver[i].x,ver[j].x,ver[i].y,ver[j].y));
		}
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y,0.0);
	}
	sort(arc+1,arc+1+tot,cmp);
	int num=0;
	double ans=0;
	for(int i=1;i<=tot;i++)
	{
		if(!search_(arc[i].st,arc[i].ed))
		{
			ans+=arc[i].we;
			num++;
			union_(arc[i].st,arc[i].ed);
		}
		
	}
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}

void init()
{
	for(int i=0;i<EDG;i++)
	{
		parent[i]=i;
		arc[i].we=0x3f3f3f3f;
	}
}
int find(int x)
{
	int x_root=x;
	while(x_root!=parent[x_root])
	{
		x_root=parent[x_root];
	}
	while(x_root!=x)
	{
		int tmp=parent[x];
		parent[x]=x_root;
		x=tmp;
	}
	return x_root;
}
int union_(int x,int y)
{
	int x_root=find(x);
	int y_root=find(y);
	if(x_root==y_root) return 0;
	parent[x_root]=y_root;
	return 1;
}
int search_(int x,int y)
{
	return find(x)==find(y);
}
2020/6/3 15:50
加载中...