10034 - Freckles solution.

Problem link: here

Description:
xy প্লেনে কতোগুলো পয়েন্ট দেয়া আছে । এক পয়েন্ট থেকে আরেক পয়েন্ট এ যাওয়ার খরচ হচ্ছে তাদের মধ্যকার দূরত্বের সমান।
বের করতে হবে সবচেয়ে কম কত খরচে সবগুলো পয়েন্ট ভিজিট করা যাবে। (এক্ষেত্রে একেকটি পয়েন্ট একাধিকবার ভিজিট হলেও সমস্যা নাই).

Solution:
সবগুলো পয়েন্ট নিজেদের মধ্যে যোগ করে একটা কমপ্লিট গ্রাফ তৈরি করে সেখান থেকে MST করলেই কাঙ্ক্ষিত উত্তর পাওয়া যায়।
যেহেতু সর্বোচ্চ পয়েন্ট 100 টি তাই কমপ্লিট গ্রাফের edge সংখ্যা হবে সর্বোচ্চ 4590। n(n − 1)/2

code:

#include<bits/stdc++.h>
using namespace std;
#define pdd pair<double,double>
#define pii pair<int,int>
#define pdp pair<double,pii>

vector <pdp> adj;
map<pdd,int> mp1;
map <int,pdd> mp2;
int node=0,edge=0;
int par[105],sz[106];
double distance(int u,int v)
{
    double x1 = mp2[u].first;
    double y1 = mp2[u].second;
    double x2 = mp2[v].first;
    double y2 = mp2[v].second;
    double x = (x1-x2);
    double y = (y1-y2);
    return sqrt(x*x + y*y);
}


struct union_find
{
    int n;
    union_find(int n)
    {
        for (int i=0;i<n;i++) sz[i]=1,par[i]=i;
    }
    int root(int a)
    {
        while(par[a]!=a)
        {
            par[a] = par[par[a]];
            a = par[a];
        }
        return a;
    }
    bool isSame(int a,int b)
    {
        return root(a)==root(b);
    }
    void make_union(int a,int b)
    {
        int i = root(a);
        int j = root(b);
        if (sz[i]<sz[j])
        {
            par[i]=j;
            sz[j]+=sz[i];
        }
        else
        {
            par[j]=i;
            sz[i]+=sz[j];
        }
    }
};
double  Kruskal()
{
    union_find UF(105);
    double total=0;
    for (int i=0;i<edge;i++)
    {
        int u = adj[i].second.first;
        int v = adj[i].second.second;
        double cost = adj[i].first;
        if (! UF.isSame(u,v))
        {
            UF.make_union(u,v);
            total+=cost;
        }
    }
    return total;
}

int main()
{
    int tc;
    cin>>tc;
    while(tc--)
    {
        cin.ignore();
        int n;
        cin>>n;
        node = n;
        for (int i=0;i<n;i++)
        {
            double x1,y1;
            cin>>x1>>y1;
            mp1[pdd(x1,y1)] = i;
            mp2[i]=pdd(x1,y1);
            for (int j=0;j<i;j++)
            {
                int u = i;
                int v = j;
                double cost = distance(u,v);
                adj.push_back(pdp(cost,pii(u,v)));
            }
        }
        double total = 0;
        edge = adj.size();
        sort(adj.begin(),adj.end());
        edge = adj.size();
        total = Kruskal();
        printf("%.2lf\n",total);
        if (tc) puts("");
        adj.clear();
        mp1.clear();
        mp2.clear();
    }
    return 0;
}