Cod sursa(job #2644427)

Utilizator vladpasarePasare Vladut Flavius vladpasare Data 24 august 2020 16:18:39
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream f("desen.in");
ofstream g("desen.out");

vector <int> Node[1001];

int n, index, l, T[1001], R[1001];

  struct Edge
  {
      int x, y;

       double distance;

  }E[499501]; //possible number of edges



bool method(Edge a, Edge b)
{
    return a.distance < b.distance;  //or'='
}

int find(int x)
{
    if (T[x] == x)return x;

    else  return T[x] = find(T[x]);
}

void Union(int x, int y)
{
    if (R[x] > R[y]) T[y] = x;

    if (R[y] > R[x])T[x] = y;

    if (R[x] == R[y])
    {
        T[x] = y;
        R[y]++;
    }
}

void read()
{
    f >> n;

    for (int i = 1; i <= n; i++)
    {
        int x, y;

        f >> x >> y;

        Node[i].push_back(x);
        Node[i].push_back(y);

        double S = 0;

        for (int j = 1; j <= i; j++)
        {
            T[j] = j; R[j] = 1;
        }

            for (int j = 1; j <= i; j++) {

                E[++index].distance = sqrt(pow(Node[i][0] - Node[j][0], 2) + pow(Node[i][1] - Node[j][1], 2));

                E[index].x = i; E[index].y = j;
            }

        sort(E + 1, E + index + 1, method);

        for (int j = 1; j <= index; j++)
        {
            int fx = find(E[j].x), fy = find(E[j].y);

            if (fx != fy)
            {
                Union(fx, fy);

                S += E[j].distance;
            }
        }

        g << fixed << setprecision(8) << S << '\n';
    }
}

  int main()
{
      read();
}