Cod sursa(job #965585)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 24 iunie 2013 11:20:10
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

#define N 105
#define aa second.first
#define bb second.second

ifstream fin("desen.in");
ofstream fout("desen.out");

int n, m, t[N];
double sol;
typedef pair <int, int> muchie;
typedef pair <double, muchie> arbore;
vector <arbore> graf;
vector <muchie> nod;
vector <bool> rez;

double cost(int x, int y, int a, int b)
{
    double dx = a-x, dy = b - y;
    return sqrt(dx*dx + dy*dy);
}

int tata(int x)
{
    if(t[x] != x) t[x] = tata(t[x]);
    return t[x];
}

void apm(int nn)
{
    for(int i=0; rez.size() < nn-1 && i < m; i++)
    {
        int x = tata(graf[i].aa), y = tata(graf[i].bb);
        if(x != y)
        {
            t[x] = y;
            sol += graf[i].first;
            rez.push_back(1);
        }
    }
}

int main()
{
    fin>>n;
    nod.push_back(muchie(0, 0));
    for(int i=1; i<=n; i++)
    {
        int x, y;
        fin>>x>>y;
        nod.push_back(muchie(x, y));

        for(int j=1; j<nod.size()-1; j++)
        {
            double c = cost(x, y, nod[j].first, nod[j].second);
            graf.push_back(arbore(c, muchie(j, i)));
        }
        for(int k=1; k<=i; k++) t[k] = k;
        sol = 0;
        sort(graf.begin(), graf.end());
        rez.clear(); m = graf.size();
        apm(i);
        fout<<fixed<<sol<<setprecision(6)<<'\n';
    }

    return 0;
}