Advertisement
Korotkodul

ои4 B СНМ

Sep 14th, 2022
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17.     for (auto x: v) cout<<x<<' ';
  18.     cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22.     for (auto x: v) cout<<x<<' ';
  23.     cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28.     for (auto x: v) cv(x);
  29.     cout<<"\n";
  30. }
  31.  
  32. void cvb(vector <bool> v){
  33.     for (bool x: v) cout<<x<<' ';
  34.     cout<<"\n";
  35. }
  36.  
  37. void cvs(vector <string>  v){
  38.     for (auto a: v){
  39.         cout<<a<<"\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a){
  44.     for (auto p: a){
  45.         cout<<p.first<<' '<<p.second<<"\n";
  46.     }
  47.     cout<<"\n";
  48. }
  49. int n,m,A,B;
  50. struct ed{
  51.     int a,b,l;
  52. };
  53. vector <ed> E;
  54.  
  55. vector <int> pr,sz;
  56.  
  57. bool sh = 1;
  58.  
  59. int getp(int v){
  60.     if (pr[v] == v){
  61.         return v;
  62.     }
  63.     int p = getp(v);
  64.     pr[v] = p;
  65.     return p;
  66. }
  67.  
  68. void un(int a, int b){
  69.     a = getp(a);
  70.     b = getp(b);
  71.     if (sh){
  72.         cout<<"PAR a b = "<<a<<' '<<b<<"\n";
  73.     }
  74.     if (a == b)return;
  75.     //sz[b] > sz[a]
  76.     if (sz[a] > sz[b]) swap(a,b);
  77.     sz[b] += sz[a];
  78.     pr[a] = b;
  79. }
  80.  
  81. int main()
  82. {
  83.     /*ios::sync_with_stdio(0);
  84.     cin.tie(0);
  85.     cout.tie(0);*/
  86.     cin>>n>>m;
  87.     map <pii, int> mtr;
  88.     for (int i = 0; i < m; ++i){
  89.             int a,b,l;
  90.             cin>>a>>b>>l;
  91.             a--;
  92.             b--;
  93.             if (a > b) swap(a,b);
  94.             if (mtr.find({a,b}) == mtr.end()){
  95.                 mtr[{a,b}] = l;
  96.             }
  97.             else{
  98.                 mtr[{a,b}] = max(mtr[{a,b}], l);
  99.             }
  100.     }
  101.     cin>>A>>B;
  102.     for (auto p: mtr){
  103.         //cout<<p.first.first<<' '<<p.first.second<<' '<<p.second<<"\n";
  104.         E.push_back({p.first.first, p.first.second, p.second});
  105.     }
  106.     pr.resize(n);
  107.     sz.assign(n,1);
  108.     for (int i = 0; i < n; ++i){
  109.         pr[i] = i;
  110.     }
  111.     /*if (sh){
  112.         cout<<"sz\n";
  113.         cv(sz);
  114.         cout<<"pr\n";
  115.         cv(pr);
  116.     }*/
  117.     for (ed e: E){
  118.         if (sh){
  119.             cout<<"a b = "<<e.a<<' '<<e.b<<"\n";
  120.         }
  121.         un(e.a, e.b);
  122.     }
  123.     /*if (sh){
  124.         cout<<"sz\n";
  125.         cv(sz);
  126.         cout<<"pr\n";
  127.         cv(pr);
  128.     }*/
  129.  
  130. }
  131. /*
  132. 6 8
  133. 1 2 3
  134. 1 3 2
  135. 1 4 4
  136. 1 6 5
  137. 2 3 15
  138. 3 6 8
  139. 3 5 7
  140. 4 5 1
  141. 1 5
  142.  
  143. */
  144.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement