哪错了啊?错哪了啊?哪啊错了?
查看原帖
哪错了啊?错哪了啊?哪啊错了?
776799
GODTREE楼主2023/7/5 16:27
#include <bits/stdc++.h>
using namespace std;
int n,m,f[5005];int sum=0,num=0;
struct edge
{
	int nxt,to,val;
}e[5005];
bool cmp(edge a,edge b)
{
	return a.val<b.val;
}
int get_f(int u)
{
	if (f[u]==0)
	{
		return u;
	}
	return get_f(f[u]);
}
void kru()
{
	for (int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	sort(e+1,e+m+1,cmp);
	for (int i=1;i<=m;i++)
	{
		f[e[i].nxt]=get_f(e[i].nxt);
		f[e[i].to]=get_f(e[i].to);
		if (f[e[i].nxt]!=f[e[i].to])
		{
			num++;
			sum+=e[i].val;
			f[e[i].nxt]=e[i].to;
		}
		if (num==n-1)
		{
			break;
		}
	}
}  
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].nxt>>e[i].to>>e[i].val;
	}
	kru();
	if(num<n-1)
	{
		cout<<"orz";
	}
	else
	{
		cout<<sum;
	}
	return 0;
}
2023/7/5 16:27
加载中...