社区讨论

神奇的并查集(结果爆0),哪位大佬帮忙看看qwq

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

讨论操作

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

当前回复
15 条
当前快照
1 份
快照标识符
@mi6wa18u
此快照首次捕获于
2025/11/20 11:51
4 个月前
此快照最后确认于
2025/11/20 14:59
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>

using namespace std;
int f[5005],a[200005],c[200005],d[200005];
int sd=0,t=1;
int n,m;
void bbs()
{
	for(int i=2;i<=m;i++)
		for(int j=1;j<i;j++)
			if(a[i]<a[j])
				swap(a[i],a[j]);
}
int gf(int x)
{
	if(f[x]==x)
		return x;
	else
		return f[x]=gf(f[x]);
}
bool merge(int x,int y,int d)
{
	int fax=gf(x);
	int fay=gf(y);
	if(fax==fay)
		return false;
	t++;
	sd+=d;
	f[fay]=fax;
}

int main()
{
	cin >> n >> m;	
	for(int i=1;i<=n;i++)
		f[i]=i;
	for(int i=1;i<=m;i++)
		cin >> c[i] >> d[i] >> a[i];
	bbs();
	for(int i=1;i<=m;i++)
	{
		merge(c[i],d[i],a[i]);
		if(t==n)
		{
			cout << sd;
			return 0;  
		}
	}
	cout << "orz";
	return 0;
}

回复

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

正在加载回复...