求助,对着书打都没打对
查看原帖
求助,对着书打都没打对
119643
潜水的蒟蒻楼主2022/10/29 11:08

kruskal算法 对着书打的
但是测试样例时输出的就是orz,没看出来哪里有问题

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,f[5005],ans;
struct fff
{
	int z,x,y;
}d[200005];
int find(int k)//并查集路径压缩
{
	if(f[k]==k)return k;
	return f[k]=find(f[k]);
}
bool cmp(fff a,fff b)
{
	return a.z<b.z;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)cin>>d[i].z>>d[i].x>>d[i].y;
	sort(d+1,d+m+1,cmp);
	int f1,f2,k=0;
	for(int i=1;i<=m;i++)
	{
		f1=find(d[i].x);
		f2=find(d[i].y);
		if(f1!=f2)
		{
			ans+=d[i].z;
			f[f1]=f2;//直接让祖先等于另一个祖先
			k++;//记录有多少个边加入树
			if(k==n-1)break;//如果有n-1个边,则完成了最小生成树
		}
	}
	if(k<n-1)cout<<"orz";
	else cout<<ans;
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

2022/10/29 11:08
加载中...