OIQ

Untitled

OIQ
Dec 8th, 2021
913
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include "utility"
  3.  
  4. struct Node {
  5.     int first;
  6.     int second;
  7.     int weight;
  8.  
  9.     inline bool operator<(const Node& other) const {
  10.         return weight <= other.weight;
  11.     }
  12.  
  13.     inline bool operator==(const Node& other) const {
  14.         return first == other.first && second == other.second && weight == other.weight;
  15.     }
  16. };
  17.  
  18. class Mst {
  19. private:
  20.     int64_t weight_min_;
  21.     int64_t weight_pre_min_;
  22.     int* parent_;
  23.     Node* order_;
  24.     Node* edges_;
  25.     int edges_size_;
  26.     int size_;
  27.  
  28. public:
  29.     explicit Mst(int size, int edges)
  30.         : weight_min_(0), weight_pre_min_(1e9), size_(size), edges_size_(edges) {
  31.         parent_ = new int[size_ + 1];
  32.         edges_ = new Node[edges_size_ + 1];
  33.         order_ = new Node[size_];
  34.         for (int i = 1; i <= size; ++i) {
  35.             parent_[i] = i;
  36.         }
  37.     }
  38.     ~Mst() {
  39.         delete[] parent_;
  40.         delete[] edges_;
  41.         delete[] order_;
  42.     }
  43.  
  44.     void input() {
  45.         for (int first, second, weight, i = 1; i <= edges_size_; ++i) {
  46.             std::cin >> first >> second >> weight;
  47.             edges_[i] = Node{first, second, weight};
  48.         }
  49.         quickSort(1, edges_size_);
  50.     }
  51.     void getMst() {
  52.         weight_min_ = getWeight(order_);
  53.         for (int i = 1; i <= size_; ++i) {
  54.             parent_[i] = i;
  55.         }
  56.         Node* order = new Node[size_];
  57.  
  58.         for (int ind = 1; ind <= edges_size_; ++ind) {
  59.             int tmp = edges_[ind].weight;
  60.             edges_[ind].weight = -1;
  61.  
  62.             int64_t pre_min = getWeight(order);
  63.             bool correct = true;
  64.             bool another = false;
  65.  
  66.             for (int i = 1; i < size_; ++i) {
  67.                 if (!(order_[i] == order[i])) {
  68.                     another = true;
  69.                     break;
  70.                 }
  71.             }
  72.  
  73.             for (int parent = getParent(1), j = 2; j <= size_; ++j) {
  74.                 if (getParent(j) != parent) {
  75.                     correct = false;
  76.                     break;
  77.                 }
  78.             }
  79.  
  80.             if (correct && another) {
  81.                 weight_pre_min_ = weight_pre_min_ < pre_min ? weight_pre_min_ : pre_min;
  82.             }
  83.  
  84.             for (int i = 1; i <= size_; ++i) {
  85.                 parent_[i] = i;
  86.             }
  87.  
  88.             edges_[ind].weight = tmp;
  89.         }
  90.  
  91.         delete[] order;
  92.     }
  93.  
  94.     int64_t getWeight(Node* order) {
  95.         int weight = 0;
  96.         int index = 1;
  97.         for (int i = 1; i <= edges_size_; ++i) {
  98.             if (edges_[i].weight > 0 && getParent(edges_[i].first) != getParent(edges_[i].second)) {
  99.                 unionNodes(edges_[i].first, edges_[i].second);
  100.                 weight += edges_[i].weight;
  101.                 order[index++] = edges_[i];
  102.             }
  103.         }
  104.  
  105.         return weight;
  106.     }
  107.  
  108.     void getResult() const {
  109.         std::cout << weight_min_ << " " << weight_pre_min_ << "\n";
  110.     }
  111.  
  112. private:
  113.     int getParent(int node) {
  114.         if (parent_[node] == node) {
  115.             return node;
  116.         }
  117.         int node_parent = getParent(parent_[node]);
  118.         parent_[node] = node_parent;
  119.         return parent_[node];
  120.     }
  121.  
  122.     void unionNodes(int first, int second) {
  123.         first = getParent(first);
  124.         second = getParent(second);
  125.         if (first != second) {
  126.             parent_[first] = second;
  127.         }
  128.     }
  129.  
  130.     void swap(Node* first, Node* second) {
  131.         Node tmp = *first;
  132.         *first = *second;
  133.         *second = tmp;
  134.     }
  135.  
  136.     int partition(int low, int high) {
  137.         int pivot = high;
  138.         int ind = (low - 1);
  139.         for (int j = low; j <= high - 1; ++j) {
  140.             if (edges_[j] < edges_[pivot]) {
  141.                 ind++;
  142.                 swap(&edges_[ind], &edges_[j]);
  143.             }
  144.         }
  145.         swap(&edges_[ind + 1], &edges_[high]);
  146.         return (ind + 1);
  147.     }
  148.  
  149.     void quickSort(int left, int right) {
  150.         if (left < right) {
  151.             int pi = partition(left, right);
  152.             quickSort(left, pi - 1);
  153.             quickSort(pi + 1, right);
  154.         }
  155.     }
  156. };
  157.  
  158. void fastIO() {
  159.     std::ios_base::sync_with_stdio(false);
  160.     std::cin.tie(nullptr);
  161.     std::cout.tie(nullptr);
  162. }
  163.  
  164. int main() {
  165.     fastIO();
  166.     int nodes, edges;
  167.     std::cin >> nodes >> edges;
  168.     Mst mst(nodes, edges);
  169.     mst.input();
  170.     mst.getMst();
  171.     mst.getResult();
  172.     return 0;
  173. }
  174.  
RAW Paste Data