Advertisement
NgJaBach

Kruskal

Jan 8th, 2022 (edited)
1,223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. // NgJaBach: Forever Meadow <3
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  7. typedef long long int ll;
  8. typedef unsigned long long ull;
  9. #define pb push_back
  10. #define pob pop_back
  11. #define mp make_pair
  12. #define upb upper_bound
  13. #define lwb lower_bound
  14. #define bend(a) a.begin(),a.end()
  15. #define rev(x) reverse(bend(x))
  16. #define mset(a) memset(a, 0, sizeof(a))
  17. #define fi first
  18. #define se second
  19. #define gcd __gcd
  20. #define getl(s) getline(cin, s);
  21. #define setpre(x) fixed << setprecision(x)
  22. #define endl '\n'
  23. const int N=100050,M=1000000007;
  24. const ll INF=1e18+7;
  25. int cha[N],cha_size[N];
  26. int find_cha(int u){
  27.     if(cha[u]==u) return u;
  28.     return cha[u]=find_cha(cha[u]);
  29. }
  30. bool European_Union(int u,int v){
  31.     int a,b;
  32.     a=find_cha(u); b=find_cha(v);
  33.     if(a==b) return false;
  34.     if(cha_size[a]<cha_size[b]) swap(a,b);
  35.     cha[b]=a;
  36.     cha_size[a]+=cha_size[b];
  37.     return true;
  38. }
  39. int main(){
  40.     ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
  41.     freopen("MST.inp","r",stdin);
  42.     freopen("MST.out","w",stdout);
  43.     int n,m,x,y,cnt;
  44.     ll z,sum=0;
  45.     vector<pair<ll,pair<int,int> > >gay;
  46.     cin>>n>>m;
  47.     cnt=n;
  48.     for(int i=1;i<=n;++i){
  49.         cha[i]=i;
  50.         cha_size[i]=1;
  51.     }
  52.     for(int i=0;i<m;++i){
  53.         cin>>x>>y>>z;
  54.         gay.pb({z,{x,y}});
  55.     }
  56.     sort(bend(gay));
  57.     for(int i=0;i<m;++i){
  58.         x=gay[i].se.fi; y=gay[i].se.se; z=gay[i].fi;
  59.         if(European_Union(x,y)){
  60.             sum+=z;
  61.             --cnt;
  62.         }
  63.     }
  64.     if(cnt>1) sum=-1;
  65.     cout<<sum;
  66.     return 0;
  67. }
  68. /*
  69. ==================================+
  70. INPUT:                            |
  71. ------------------------------    |
  72.  
  73. ------------------------------    |
  74. ==================================+
  75. OUTPUT:                           |
  76. ------------------------------    |
  77.  
  78. ------------------------------    |
  79. ==================================+
  80. */
  81.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement