SHARE
TWEET

Untitled

a guest Nov 19th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. struct edge{                    // структура для ребра вес-вершина1-вершина2
  9.     int w, v1, v2;
  10. };
  11.  
  12. struct king {                   // структура для хранения "имени" короля и количества "подданных"
  13.     int name, num;
  14. };
  15.  
  16. bool cmp(edge v1, edge v2) {
  17.     return v1.w < v2.w;
  18. }
  19.  
  20. vector <edge> edges;
  21. vector <king> kingdom;
  22.  
  23. int n, m, sum;
  24.  
  25. int find_king(int v) {
  26.     if (kingdom[v].name == v)return kingdom[v].name;    // если вершина - сама себе король, возвращаем её
  27.     kingdom[v] = kingdom[find_king(kingdom[v].name)];   // иначе "спрашиваем" у её правителя
  28.     return kingdom[v].name;
  29. }
  30.  
  31. void unite(int v1, int v2) {
  32.     if (kingdom[v1].num > kingdom[v2].num)swap(v1, v2); // Проверяем размер "стран" что бы понять, какая должна присоединиться
  33.  
  34.     kingdom[v1] = { v2, kingdom[v2].num + kingdom[v1].num };
  35. }
  36.  
  37. int main()
  38. {
  39.     cin >> n >> m;
  40.     for (int i = 0; i < n; i++)kingdom.push_back({ i,1 });  // указываем каждую вершину в правители саму для себя
  41.     for (int i = 0; i < m; i++) {
  42.         int x, y, z;
  43.         cin >> x >> y >> z;
  44.         edges.push_back({ z,x-1,y-1 }); //-1, так как нумерация в программе идёт с '0', а во входных данных зачастую с '1'
  45.     }
  46.     sort(edges.begin(),edges.end(),cmp); // сортируем рёбра в порядке неубывания
  47.     for (int i = 0; i < m; i++) {
  48.         int v1 = find_king(edges[i].v1); // находим короля первой вершины
  49.         int v2 = find_king(edges[i].v2); // короля второй
  50.         int w = edges[i].w;
  51.         if (v1 != v2) {                 // если король разный - объединяем
  52.             sum += w;
  53.             cout << v1 << ' ' << v2 << ' ' << w << '\n';
  54.             unite(v1, v2);
  55.         }
  56.     }
  57.  
  58.     cout << sum;
  59.     return 0;
  60.  
  61. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top