Kruskal 44pts HELP TREE!
查看原帖
Kruskal 44pts HELP TREE!
519092
阿宁已被领养楼主2022/9/26 19:40

记录如下,下了第三个测试点但是数据有点多看的眼都花了qwq

评测记录

数据还是不放了吧,太多了谁会手推五十个点的最小生成树啊qwq

代码如下

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n,m,x,y,z,f[1000000],ans=0,qwq=0;
struct gs
{
	ll a,b,c;
}bian[1000000];
bool cmp(gs g,gs s)
{
	return g.c<s.c;
}
ll find(ll x)
{
	if(f[x]==x) return x; 
	else find(f[x]);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) f[i]=i;
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		bian[i].a=x;
		bian[i].b=y;
		bian[i].c=z;
	}
	sort(bian+1,bian+m+1,cmp);
	//cout<<"start"<<endl;
	for(ll i=1;i<=m;i++)
	{
		ll f1=find(bian[i].a),f2=find(bian[i].b);
		if(f1!=f2)
		{
			//cout<<bian[i].a<<' '<<bian[i].b<<" "<<f1<<' '<<f2<<endl;
			if(f1==bian[i].a) f1=f2;
			f[bian[i].a]=f1;
			f[bian[i].b]=f1;
			ans+=bian[i].c;
		}
	}
	for(ll i=1;i<=n;i++)//我想的是如果图不连通会有1+个根为自己的点,先纪录下来一个,再有多的就说明不连通了 
	{
		if(f[i]==i&&qwq==1)
		{
			printf("orz");
			return 0;
		}
		else if(f[i]==i) qwq++;
	}
	printf("%lld",ans);
	return 0;
}

不胜感激!!!!

2022/9/26 19:40
加载中...