• API
• FAQ
• Tools
• Archive
daily pastebin goal
19%
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);
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);