社区讨论
16分求调
P3366【模板】最小生成树参与者 3已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @mjin6g27
- 此快照首次捕获于
- 2025/12/23 21:49 2 个月前
- 此快照最后确认于
- 2025/12/26 17:50 2 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
struct Edge{
int u,v,val;
};
vector<Edge> edges;
int ufs[N];
int Find(int x){
if(ufs[x]<0)return x;
return ufs[x]=Find(ufs[x]);
}
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x==y)return;
ufs[x]+=ufs[y];
ufs[y]=x;
}
int main(){
memset(ufs,-1,sizeof ufs);
int cnt=0,sum=0,total=0;
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int u,v,val;
cin>>u>>v>>val;
edges.push_back({u,v,val});
total+=val;
}
sort(edges.begin(),edges.end(),[](const Edge& e1,const Edge& e2){
return e1.val<e2.val;
});
for(auto e:edges)
{
if(cnt>=n-1)break;
if(Find(e.u)==Find(e.v))continue;
sum+=e.val;
Union(e.u,e.v);
cnt++;
}
if(cnt==n-1)cout<<total-sum;
else cout<<"orz";
return 0;
}
(怀疑只对了一个输出orz的点)
回复
共 10 条回复,欢迎继续交流。
正在加载回复...