Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <time.h>
  4. #include <vector>
  5. #include <string>
  6. #include <set>
  7. #include <utility>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <iomanip>
  11. #include <cmath>
  12. #include <limits>
  13.  
  14. using std::vector;
  15. using std::cout;
  16. using std::endl;
  17. using std::cin;
  18. using std::string;
  19. using std::set;
  20. using std::pair;
  21. using std::make_pair;
  22. using std::min;
  23. using std::queue;
  24.  
  25.  
  26. struct edge {
  27. int number;
  28. int from;
  29. int to;
  30. long long weight;
  31.  
  32. edge(int number, int from, int to, long long weight) :
  33. number(number),
  34. from(from),
  35. to(to),
  36. weight(weight) {}
  37. };
  38.  
  39.  
  40. vector<int> findcomp(int number, vector<vector<int>> &gg) {
  41. vector<bool> visited(number, false);
  42. vector<int> comp(number + 1, -1);
  43. int cur = 0;
  44. for (int iii = 0; iii < number; ++iii) {
  45. if (!visited[iii]) {
  46. queue<int> q;
  47. q.push(iii);
  48. while (!q.empty()) {
  49. int vv = q.front();
  50. q.pop();
  51. visited[vv] = true;
  52. comp[vv] = cur;
  53. for (uint64_t j = 0; j < gg[vv].size(); ++j) {
  54. if (!visited[gg[vv][j]])
  55. q.push(gg[vv][j]);
  56. }
  57. }
  58. cur++;
  59. }
  60. }
  61. comp[number] = cur;
  62. return comp;
  63. }
  64.  
  65. vector<edge> boruvka(uint64_t number, vector<edge> &edges) {
  66. int mm = edges.size();
  67. edges.push_back(edge(0, 0, 0, std::numeric_limits<long long>::max()));
  68. vector<vector<int>> gg(number, vector<int>(0));
  69. vector<edge> ttt(0, edge(0, 0, 0, 0));
  70. vector<bool> visited(mm, false);
  71. vector<int> comp(number + 1, 0);
  72. while (ttt.size() < number - 1) {
  73. comp = findcomp(number, gg);
  74. int kol = comp[number];
  75. vector<int> minEdge(kol, mm);
  76. for (uint64_t ii = 0; ii < edges.size(); ++ii) {
  77. int compF = comp[edges[ii].from], compS = comp[edges[ii].to];
  78. if (compF != compS) {
  79. if ((edges[minEdge[compF]].weight > edges[ii].weight) ||
  80. (edges[minEdge[compF]].weight) ==
  81. (edges[ii].weight && edges[minEdge[compF]].number > edges[ii].number)) {
  82. minEdge[compF] = ii;
  83. }
  84. if ((edges[minEdge[compS]].weight > edges[ii].weight) ||
  85. ((edges[minEdge[compS]].weight == edges[ii].weight) &&
  86. (edges[minEdge[compS]].number > edges[ii].number))) {
  87. minEdge[compS] = ii;
  88. }
  89. }
  90. }
  91. for (int i = 0; i < kol; ++i) {
  92. if (!visited[minEdge[i]]) {
  93. visited[minEdge[i]] = true;
  94. ttt.push_back(edges[minEdge[i]]);
  95. gg[edges[minEdge[i]].from].push_back(edges[minEdge[i]].to);
  96. gg[edges[minEdge[i]].to].push_back(edges[minEdge[i]].from);
  97. }
  98. }
  99. }
  100. return ttt;
  101. }
  102.  
  103.  
  104. int main() {
  105. int number;
  106. cin >> number;
  107. vector<pair<long long, long long>> coord(number);
  108. for (int i = 0; i < number; ++i) {
  109. cin >> coord[i].first >> coord[i].second;
  110. }
  111. edge nll(0, 0, 0, 0);
  112. int medg = number * number;
  113. vector<edge> edges(medg, nll), mst;
  114. int edgenumber = 0;
  115. for (int i = 0; i < number; ++i) {
  116. for (int j = 0; j < number; ++j) {
  117. long long val = (coord[i].first - coord[j].first) *
  118. (coord[i].first - coord[j].first) +
  119. (coord[i].second - coord[j].second) *
  120. (coord[i].second - coord[j].second);
  121. edges[edgenumber] = edge(edgenumber, i, j, val);
  122. edgenumber = edgenumber + 1;
  123. }
  124. }
  125. mst = boruvka(number, edges);
  126. double ss = 0;
  127. for (uint64_t i = 0; i < mst.size(); ++i) {
  128. ss = std::max(ss, sqrt(mst[i].weight));
  129. }
  130. cout << std::fixed << std::setprecision(10) << ss;
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement