10分的kruskal,实在不知道哪里错了,求大佬解惑
查看原帖
10分的kruskal,实在不知道哪里错了,求大佬解惑
678783
good_pig楼主2022/3/15 09:48
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxe=5001000;
const int maxv=100001;
struct Arc{
	int u;
	int v;
	double w;
}E[maxe];
bool cmp(Arc e1, Arc e2){
	return e1.w<e2.w;
} 
int father[maxv];			//并查集数组 
int n,m,cnt=0;			//cnt为边的个数 
int X[maxv],Y[maxv];
int findFather(int x){			//并查集返回根节点 
	if(x==father[x])	return x;
	int f=findFather(father[x]);	//路径压缩 
	father[x]=f;
	return f;
}
double Kruskal(){
	double ans=0.0;		//边权之和
	for(int i=1;i<=n;i++){
		father[i]=i;			//初始化,每个节点的父节点都是自己 
	} 
	sort(E,E+cnt,cmp);				//边排序
	int E_num=0;
	for(int i=0;i<cnt;i++){
		int u=E[i].u,v=E[i].v;
		int fau=findFather(u),fav=findFather(v);
		if(fau!=fav){		//该边连接的两个节点都在已加入点的集合中
			ans+=E[i].w;
			fau=father[fav];			//合并u,v节点 
			E_num++;
			if(E_num==n-1)	break;
		}		
	}
	if(E_num<n-1)	return -1;		//说明该图不连通 
	return ans;
}
int main(){
	cin>>n>>m;
	double dis;
	for(int i=1;i<=n;i++){
		cin>>X[i]>>Y[i];
	}
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			dis=(double)sqrt(pow(double(X[i]-X[j]),2)+pow(double(Y[i]-Y[j]),2));
			E[cnt].u=i,E[cnt].v=j;
			E[cnt++].w=dis;
		}
	}
	int x,y;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		E[cnt].u=x,E[cnt].v=y;
		E[cnt++].w=0.0;			//已经存在的边,边权设为0 
		
	}
	double ans=Kruskal();
	printf("%.2f",ans);
	return 0;
}
2022/3/15 09:48
加载中...