Cod sursa(job #3191936)

Utilizator divadddDavid Curca divaddd Data 10 ianuarie 2024 23:34:44
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
using namespace std;
using db = long double;
using pii = pair<int, int>;
using edge = tuple<db, int, int>;
const int NMAX = 1002;
int n;
pii v[NMAX];
vector<edge> edges;

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

struct DSU {
    int n;
    vector<int> t, sz;
    DSU(int _n){
        n = _n;
        t.resize(n+1);
        sz.resize(n+1);
        for(int i = 1; i <= n; i++){
            t[i] = i;
            sz[i] = 1;
        }
    }
    int root(int nod){
        if(t[nod] == nod){
            return nod;
        }
        return t[nod] = root(t[nod]);
    }
    void join(int x, int y){
        x = root(x);
        y = root(y);
        if(sz[x] < sz[y]){
            swap(x, y);
        }
        sz[x] += sz[y];
        t[y] = x;
    }
    bool areJoined(int x, int y){
        return root(x) == root(y);
    }
};

db sqr(db x){
    return (x*x);
}

db dist(pii a, pii b){
    return sqrt(sqr(a.first - b.first) + sqr(a.second - b.second));
}

db apm(){
    sort(edges.begin(), edges.end());
    DSU ds(n);
    db ans = 0;
    vector<edge> nw;
    for(int i = 0; i < edges.size(); i++){
        auto [cost, x, y] = edges[i];
        if(!ds.areJoined(x, y)){
            ans += cost;
            nw.push_back(edges[i]);
            ds.join(x, y);
        }
    }
    edges.clear();
    edges = nw;
    return ans;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> v[i].first >> v[i].second;
    }
    for(int i = 1; i <= n; i++){
        for(int j = i-1; j >= 1; j--){
            edges.push_back({dist(v[j], v[i]), j, i});
        }
        fout << fixed << setprecision(6) << apm() << "\n";
    }
    return 0;
}