Advertisement
Dzham

Untitled

Apr 28th, 2019
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5. #include <iomanip>
  6. #include <cmath>
  7.  
  8. class DSU {
  9. std::vector<int> dsu;
  10. std::vector<int> sizes;
  11.  
  12. public:
  13. DSU(int n) {
  14. for (int i = 0; i < n; ++i) {
  15. dsu.push_back(i);
  16. }
  17. sizes.resize(n, 1);
  18. }
  19.  
  20. int find_root(int a) {
  21. if (dsu[a] == a) {
  22. return a;
  23. }
  24. return dsu[a] = find_root(dsu[a]);
  25. }
  26.  
  27. void union_dsu(int a, int b) {
  28. if (sizes[b] < sizes[a]) {
  29. dsu[b] = a;
  30. sizes[a] += sizes[b];
  31. } else {
  32. dsu[a] = b;
  33. sizes[b] += sizes[a];
  34. }
  35. }
  36.  
  37.  
  38. };
  39.  
  40. int main() {
  41. int N;
  42. std::cin >> N;
  43. int a, b;
  44. std::vector<std::vector<double>> matrix(N, std::vector<double>(N, 0));
  45. std::vector<std::pair<int, int>> points(N);
  46. for (int i = 0; i < N; ++i) {
  47. std::cin >> a >> b;
  48. points[i] = std::make_pair(a, b);
  49. }
  50. double s;
  51. for (int i = 0; i < N; ++i) {
  52. for (int j = i + 1; j < N; ++j) {
  53. s = std::pow(std::pow(points[i].first - points[j].first, 2) + std::pow(points[i].second - points[j].second, 2), 0.5);
  54. matrix[i][j] = s;
  55. }
  56. }
  57. int M;
  58. std::cin >> M;
  59. for (int i = 0; i < M; ++i) {
  60. std::cin >> a >> b;
  61. matrix[a - 1][b - 1] = 0;
  62. matrix[b - 1][a - 1] = 0;
  63. }
  64. std::vector<std::pair<double, std::pair<int, int>>> lines;
  65. for (int i = 0; i < N; ++i) {
  66. for (int j = i + 1; j < N; ++j) {
  67. lines.push_back(std::make_pair(matrix[i][j], std::make_pair(i, j)));
  68. }
  69. }
  70. DSU dsu(N);
  71. std::sort(lines.begin(), lines.end());
  72. double answer = 0;
  73. for (int i = 0; i < lines.size(); ++i) {
  74. double s = lines[i].first;
  75. int a = lines[i].second.first;
  76. int b = lines[i].second.second;
  77. int r1 = dsu.find_root(a);
  78. int r2 = dsu.find_root(b);
  79. if (r1 != r2) {
  80. answer += s;
  81. dsu.union_dsu(r1, r2);
  82. }
  83. }
  84. std::cout << std::setprecision(5) << answer << '\n';
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement