kananasgarli90

Minimal çərçivə

Sep 28th, 2020
826
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. multiset<pair<int, pair<int, int> > > edges;
  4. int n, m, u, v, w, mst;
  5. int p[20001];
  6.  
  7. void link(int x, int y){
  8.     p[x] = y;
  9. }
  10.  
  11. int find_set(int x){
  12.     if(x != p[x]){
  13.         p[x] = find_set(p[x]);
  14.     }
  15.     return p[x];
  16. }
  17. int main()
  18. {
  19.     cin>>n>>m;
  20.     while(m--){
  21.         cin>>u>>v>>w;
  22.         edges.insert(make_pair(w, make_pair(u, v)));
  23.     }
  24.     for(int i = 1; i <= n; i++){
  25.         p[i] = i;
  26.     }
  27.  
  28.     for(auto i = edges.begin(); i != edges.end(); i++){
  29.         u = (*i).second.first;
  30.         v = (*i).second.second;
  31.         w = (*i).first;
  32.         int p1 = find_set(u);
  33.         int p2 = find_set(v);
  34.         if(p1 != p2){
  35.             link(p1, p2);
  36.             mst += w;
  37.         }
  38.     }
  39.     cout<<mst<<endl;
  40. }
  41.  
  42.  
  43.  
RAW Paste Data