daily pastebin goal
67%
SHARE
TWEET

Untitled

a guest Oct 16th, 2018 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <cmath>
  5.  
  6. double edge_weight(std::pair<int, int> a, std::pair<int, int> b) {
  7.     return std::sqrt(std::pow(a.first - b.first, 2) + std::pow(a.second - b.second, 2));
  8. }
  9.  
  10. double kruskal(int ver_num, std::vector<std::pair<double, std::pair<int, int>>>& edges) {
  11.     size_t edge_num = edges.size();
  12.     std::sort(std::begin(edges), std::end(edges));
  13.     std::vector<int> treeId(ver_num);
  14.     for (int32_t i = 0; i < ver_num; i++) {
  15.         treeId[i] = i;
  16.     }
  17.     double mstCost = 0;
  18.     std::vector<std::pair<int, std::pair<int, int>>> edgesInMST;
  19.     for (int i = 0; i < edge_num; i++) {
  20.         int firstVer = edges[i].second.first, secVer = edges[i].second.second;
  21.         double cost = edges[i].first;
  22.         if (treeId[firstVer] != treeId[secVer]) {
  23.             edgesInMST.emplace_back(std::make_pair(cost, std::make_pair(firstVer, secVer)));
  24.             mstCost += cost;
  25.             int oldTree = treeId[firstVer];
  26.             for (int j = 0; j < ver_num; ++j) {
  27.                 if (treeId[j] == oldTree)
  28.                     treeId[j] = treeId[secVer];
  29.             }
  30.         }
  31.     }
  32.     return mstCost;
  33. }
  34.  
  35. int main() {
  36.     int num_terminal, num_extra;
  37.     std::cin >> num_terminal >> num_extra;
  38.     std::vector<std::pair<int, int> > vertices(num_terminal);
  39.     std::vector<std::pair<int, int> > added_vertices;
  40.     std::vector<std::pair<double, std::pair<int, int> > > edges;
  41.     for (int i = 0; i != num_terminal; ++i) {
  42.         std::cin >> vertices[i].first >> vertices[i].second;
  43.     }
  44.     int right = -1;
  45.     int down = 100000;
  46.     int up = -1;
  47.     int left = 100000;
  48.     for (int j = 0; j != num_terminal; ++j) {
  49.         if (right < vertices[j].first) {
  50.             right = vertices[j].first;
  51.         }
  52.         if (down > vertices[j].second) {
  53.             down = vertices[j].second;
  54.         }
  55.         if (up < vertices[j].second) {
  56.             up = vertices[j].second;
  57.         }
  58.         if (left > vertices[j].first) {
  59.             left = vertices[j].first;
  60.         }
  61.     }
  62.     std::cout << "OKI\n";
  63.     for (int i = 0; i != num_terminal; ++i) {
  64.         for (int j = i + 1; j < num_terminal; ++j) {
  65.             edges.emplace_back(std::make_pair(edge_weight(vertices[i], vertices[j]), std::make_pair(i, j)));
  66.         }
  67.     }
  68.     double best_mst = kruskal(num_terminal, edges);
  69.     std::cout << best_mst << "\n";
  70.     int new_num_vert = num_terminal;
  71.     int step1 = 1;
  72.     int step2 = 1;
  73.     if (right - left >= 1000) {
  74.         step1 = (right - left) / 300;
  75.     }
  76.     if (up - down >= 1000) {
  77.         step2 = (up - down) / 400;
  78.     }
  79.     std::cout << right << "\n";
  80.     for (int i = down; i < up; i += step1) {
  81.         for (int j = left; j < right && num_extra != 0; j += step2) {
  82.             std::vector<std::pair<double, std::pair<int, int> > > copy_edges = edges;
  83.             std::pair<int, int> possible_vert = std::make_pair(i, j);
  84.             for(int k = 0; k != new_num_vert; ++k) {
  85.                 copy_edges.push_back(std::make_pair(edge_weight(possible_vert, vertices[k]), std::make_pair(k, new_num_vert)));
  86.             }
  87.             double loc_mst = kruskal(new_num_vert + 1, copy_edges);
  88.             if (j == 9 && i == 1) {
  89.                 std::cout << loc_mst << "\n";
  90.             }
  91.             if (loc_mst < best_mst) {
  92.                 best_mst = loc_mst;
  93.                 edges = copy_edges;
  94.                 --num_extra;
  95.                 ++new_num_vert;
  96.                 vertices.push_back(possible_vert);
  97.                 added_vertices.push_back(possible_vert);
  98.             }
  99.         }
  100.     }
  101.     std::cout << added_vertices.size() << "\n";
  102.     for (auto x : added_vertices) {
  103.         std::cout << x.first << " " << x.second << "\n";
  104.     }
  105.     return 0;
  106. }
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
 
Top