21pts,3AC,3TLE求调
查看原帖
21pts,3AC,3TLE求调
1204744
C2204hyk楼主2024/7/28 20:18

求调``` #include<bits/stdc++.h> using namespace std; int n,m,x,y,z,tot,ans,fa[5086]; struct ed{ int x,y,z; }a[100086]; int find(int x){ while(fa[fa[x]]!=fa[x]) fa[x]=fa[fa[x]]; return fa[x]; } void merge(int x,int y){ fa[find(x)]=find(y); } bool cmp(ed x,ed y){ return x.z<y.z; } void kruskal(){ for(int i=1;i<=m;i++){ if(find(a[i].x != find(a[i].y))){ merge(a[i].x ,a[i].y ); tot++; ans+=a[i].z; if(tot==n-1) return; } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y>>a[i].z; sort(a+1,a+1+m,cmp); kruskal(); if(tot < n-1) cout<<"orz"<<endl; else cout<<ans<<endl; return 0; }

2024/7/28 20:18
加载中...