Advertisement
Guest User

Untitled

a guest
Oct 17th, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <sstream>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <fstream>
  7. #include <cmath>
  8. #include <unordered_set>
  9.  
  10. struct point{
  11. double x;
  12. double y;
  13. point (int a, int b) {
  14. x = a;
  15. y = b;
  16. }
  17. };
  18.  
  19. double dist(point a, point b) {
  20. return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  21. }
  22.  
  23. double prima (std::vector <std::vector <double>> mat) {
  24. double sum = 0;
  25. std::vector <double> range(mat.size());
  26. std::vector <bool> used(mat.size(), 0);
  27. range[0] = 0;
  28. used[0] = true;
  29. for (int i = 0; i < mat.size(); ++i) {
  30. range[i] = mat[0][i];
  31. }
  32. for (int i = 0; i < mat.size(); ++i) {
  33. int v = -1;
  34. for (int j = 0; j < mat.size(); ++j)
  35. if (!used[j] && (v == -1 || range[j] < range[v])) {
  36. sum -= range[v] - range[j];
  37. v = j;
  38. }
  39. if (v != -1) {
  40. used[v] = true;
  41. for (int j = 0; j < mat.size(); ++j)
  42. if (mat[v][j] < range[j]) {
  43. range[j] = mat[v][j];
  44. }
  45. } else {
  46. break;
  47. }
  48. }
  49. return sum;
  50. }
  51.  
  52. int main() {
  53. int a, b, n, k;
  54. std::ifstream fin("Nodes.txt");
  55. std::vector <point> vec;
  56. fin >> n >> k;
  57. std::vector <std::vector <double>> mat(n);
  58. for (int i = 0; i < n; ++i) {
  59. fin >> a >> b;
  60. point p(a, b);
  61. vec.push_back(p);
  62. }
  63. fin.close();
  64. for (int i = 0; i < n; ++i) {
  65. for (int j = 0; j < n; ++j) {
  66. mat[i].push_back(dist(vec[i], vec[j]));
  67. }
  68. }
  69. int itog = prima(mat);
  70. std::cout << prima(mat);
  71. for (int i = 0; i < n; ++i) {
  72. std::cin >> a >> b;
  73. if (a < minx) minx = a;
  74. if (a > maxx) maxx = a;
  75. if (b < miny) miny = b;
  76. if (b > maxy) maxy = b;
  77. }
  78. for()
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement