Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <sstream>
- #include <cstdlib>
- #include <ctime>
- #include <fstream>
- #include <cmath>
- #include <unordered_set>
- struct point{
- double x;
- double y;
- point (int a, int b) {
- x = a;
- y = b;
- }
- };
- double dist(point a, point b) {
- return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- double prima (std::vector <std::vector <double>> mat) {
- double sum = 0;
- std::vector <double> range(mat.size());
- std::vector <bool> used(mat.size(), 0);
- range[0] = 0;
- used[0] = true;
- for (int i = 0; i < mat.size(); ++i) {
- range[i] = mat[0][i];
- }
- for (int i = 0; i < mat.size(); ++i) {
- int v = -1;
- for (int j = 0; j < mat.size(); ++j)
- if (!used[j] && (v == -1 || range[j] < range[v])) {
- sum -= range[v] - range[j];
- v = j;
- }
- if (v != -1) {
- used[v] = true;
- for (int j = 0; j < mat.size(); ++j)
- if (mat[v][j] < range[j]) {
- range[j] = mat[v][j];
- }
- } else {
- break;
- }
- }
- return sum;
- }
- int main() {
- int a, b, n, k;
- std::ifstream fin("Nodes.txt");
- std::vector <point> vec;
- fin >> n >> k;
- std::vector <std::vector <double>> mat(n);
- for (int i = 0; i < n; ++i) {
- fin >> a >> b;
- point p(a, b);
- vec.push_back(p);
- }
- fin.close();
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- mat[i].push_back(dist(vec[i], vec[j]));
- }
- }
- int itog = prima(mat);
- std::cout << prima(mat);
- for (int i = 0; i < n; ++i) {
- std::cin >> a >> b;
- if (a < minx) minx = a;
- if (a > maxx) maxx = a;
- if (b < miny) miny = b;
- if (b > maxy) maxy = b;
- }
- for()
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement