社区讨论
Kuskal为什么错
P2126Mzc家中的男家丁参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi5ho6b0
- 此快照首次捕获于
- 2025/11/19 12:15 4 个月前
- 此快照最后确认于
- 2025/11/19 12:15 4 个月前
RT
CPP#include<bits/stdc++.h>
using namespace std;
long long n,m,i,sum,pre[20005],f;
struct pt
{
int pnt1;
int pnt2;
int tm;
} a[2300000];
bool cmp(pt x, pt y)
{
return x.tm<y.tm;
}
int sch(int x)
{
if (pre[x]==x) return pre[x];
pre[x]=sch(pre[x]);
return pre[x];
}
int main()
{
cin>>n>>m;
for (i=1;i<=m;i++)
{
cin>>a[i].pnt1>>a[i].pnt2>>a[i].tm;
}
for (i=0;i<=n+1;i++) pre[i]=i;
sort(a+1,a+m+1,cmp);
i=-1;
while (f<n)
{
i++;
if (sch(a[i].pnt1)!=sch(a[i].pnt2))
{
pre[sch(a[i].pnt1)]=sch(a[i].pnt2);
sum+=a[i].tm;
f++;
}
}
cout<<sum;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...