1 条题解
-
0
#include <bits/stdc++.h> #define ll long long using namespace std; const ll N=100005,M=300005; struct node1{ ll x,y,dist; bool operator<(node1 k)const{ return dist<k.dist; } }a[M]; ll n,m,k,s,t,tot,fa[N]; ll ans,ans1,z,zz; int getfa(ll x){ if (fa[x]==x) return x; fa[x]=getfa(fa[x]); return fa[x]; } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>n>>m; for (int i=1;i<=m;++i) cin>>a[i].x>>a[i].y>>a[i].dist; sort(a+1,a+1+m); for (int i=1;i<=n;++i) fa[i]=i; z=0;zz=0; for (int i=1;i<=m;++i){ s=getfa(a[i].x); t=getfa(a[i].y); if (s!=t){ ++zz; z+=a[i].dist; fa[s]=t; } } if (zz==n-1) cout<<z; else cout<<"orz"; }
- 1
信息
- ID
- 820
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 6
- 已通过
- 2
- 上传者