社区讨论
神奇的并查集(结果爆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 条回复,欢迎继续交流。
正在加载回复...