社区讨论

16分求调!!!

P3366【模板】最小生成树参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhj2y2bh
此快照首次捕获于
2025/11/03 19:51
4 个月前
此快照最后确认于
2025/11/03 19:51
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,m,sum;
long long x,y,z;
long long maxn[1000001];
struct abc
{
	long long a,b,c;	
}o[1000001];
bool cmp(abc q,abc p)
{
	return q.c<p.c;
}
long long find(long long u)
{
	if(u!=maxn[u]) return find(maxn[u]);
	return maxn[u];
}
int main()
{
	cin>>n>>m;
	for(long long i=1;i<=n;i++) maxn[i]=i;
	for(long long i=1;i<=m;i++)
	{	
		cin>>o[i].a>>o[i].b>>o[i].c;		
	}
	sort(o+1,o+1+m,cmp);
	for(long long i=1;i<=m;i++)
	{
		if(find(o[i].a)!=find(o[i].b))
		{
			maxn[find(o[i].b)]=find(o[i].a);
			sum+=o[i].c;
		}
	} 
	for(long long i=1,p;i<=n;i++)
	{
		if(p==2)
		{
			cout<<"orz";
			return 0;
		}
		if(maxn[i]=i) p++;
	}
	cout<<sum;
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...