Tmp isa

// Solutie Flux
// Tinca Matei
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 8;
int x[2*MAX_N], y[2*MAX_N];
int num[2*MAX_N];

// Clasa de flux maxim de cost minim
class MinCostMaxFlow {
    int n, src, dest;

    // Lista de adiacenta
    vector<int> graph[1+2*MAX_N+1];

    // Capacitatile pe fiecare muchie
    int kappa[1+2*MAX_N+1][1+2*MAX_N+1];

    // Fluxul transmis pe fiecare muchie
    int flow[1+2*MAX_N+1][1+2*MAX_N+1];

    // Parintele unui nod in arborele de la Bellman-Ford
    int papa[1+2*MAX_N+1];

    // costul unei muchii din graf
    double cost[1+2*MAX_N+1][1+2*MAX_N+1];

    // Cel mai bun cost de la sursa pana la nodul curent
    double bestcost[1+2*MAX_N+1];

    // Pompeaza flux de la sursa la destinatie pe drumul in arborele de la Bellman-Ford
    void pump(int nod) {
        int i = nod;
        int fl = 10;
        // Initial trebuie sa calculam cat flux pompam pe drumul respectiv
        while(i != src) {
            fl = min(fl, kappa[papa[i]][i] - flow[papa[i]][i]);
            i = papa[i];
        }

        // Pompam fluxul propriu-zis pe drumul din arborele Bellman-Ford
        while(nod != 0) {
            flow[papa[nod]][nod] += fl;
            flow[nod][papa[nod]] -= fl;
            nod = papa[nod];
        }

        // Reactualizam cantitatea pompata de flux in total si costul in total
        maxfl += fl;
        mincost += bestcost[dest] * fl;
    }

    // Baga Bellman-Ford; returneaza true daca a gasit un drum pe care poate pompa flux de la sursa la destinatie
    bool bellmanford() {
        deque<pair<int, double> > q;

        // Initializam toate costurile cu infinit, in afara de costul sursei care va fi 0
        for(int i = 0; i < n; ++i)
            bestcost[i] = 1000000000.0f;
        bestcost[src] = 0.0f;

        // Bagam sursa in coada
        q.push_back(make_pair(src, 0.0f));

        while(!q.empty()) {
            // Scoatem primul element din coada
            int nod = q.front().first;
            double costnod = q.front().second;
            q.pop_front();

            // Reactualizam costurile minime pt fiecare vecin
            for(auto it: graph[nod]) {
                if(flow[nod][it] < kappa[nod][it] && bestcost[nod] + cost[nod][it] < bestcost[it]) {
                    bestcost[it] = bestcost[nod] + cost[nod][it];
                    q.push_back(make_pair(it, bestcost[it]));
                    papa[it] = nod;
                }
            }
        }

        // Exista drum de la sursa pana la destinatie
        if(bestcost[dest] < 1000000000.0f) {
            pump(dest);
            return true;
        }
        return false;
    }

public:
    int maxfl;
    double mincost;

    // Initializeaza toate variabilele interne
    MinCostMaxFlow(int _n) {
        n = _n;
        src = 0;
        dest = n - 1;
        maxfl = mincost = 0;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                kappa[i][j] = flow[i][j] = cost[i][j] = 0;
    }

    // Adauga o muchie de la nodul a la nodul b cu capacitate k si cost c
    void pushEdge(int a, int b, int k, double c) {
        graph[a].push_back(b);
        graph[b].push_back(a);
        cost[a][b] = c;
        cost[b][a] = -c;
        kappa[a][b] = k;
    }

    // Ruleaza algoritmul de flux
    void runFlow() {
        while(bellmanford());
    }
};

// Returneaza patratul lui x
double sqr(double x) {
    return x * x;
}

// Returneaza distanta dintre doua puncte (x1, y1), (x2, y2)
double dist(double x1, double y1, double x2, double y2) {
    return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}

int main() {
    int n;
    double rez = 1000000000.0f;

    // Citirea numerelor
    FILE *fin = fopen("xd.in", "r");
    fscanf(fin, "%d", &n);
    for(int i = 0; i < 2 * n; ++i)
        fscanf(fin, "%d%d", &x[i], &y[i]);
    fclose(fin);

    // Impart toate casele in doua submultimi. Intre doua case din submultimi diferite
    // adaug o muchie de capacitate 1 si cost egal cu distanta dintre cele doua puncte
    for(int i = 0; i < (1 << (2 * n)); ++i) {
        int cnt = 0;
        // Renumerotam toate casele; Cele din multimea A vor fi numerotate de la 1 pana la n,
        // iar cele din multimea B vor fi numerotate de la n + 1 pana la 2 * n
        for(int j = 0; j < 2 * n; ++j)
            if((1 << j) & i) {
                cnt++;
                num[j] = cnt;
            } else
                num[j] = n + (j + 1) - cnt;

        if(cnt == n) {
            MinCostMaxFlow flx(2 * n + 2);

            // Construirea propriu-zisa a grafului
            for(int a = 0; a < 2 * n; ++a) {
                for(int b = 0; b < 2 * n; ++b)
                    if(((1 << a) & i) > 0 && ((1 << b) & i) == 0)
                        flx.pushEdge(num[a], num[b], 1, dist(x[a], y[a], x[b], y[b]));

                // Adaug o muchie de la sursa la fiecare nod din multimea A
                if((1 << a) & i)
                    flx.pushEdge(0, num[a], 1, 0);
                else // Adaug o muchie de la fiecare nod din multimea B la destinatie
                    flx.pushEdge(num[a], 2 * n + 1, 1, 0);
            }

            // Rulez fluxul pe graful construit
            flx.runFlow();

            // In graful construit, cuplajul trebuie sa fie perfect!!!
            assert(flx.maxfl == n);

            // reactualizam rezultatul
            rez = min(rez, flx.mincost);
        }
    }

    // Afisam rezultatele
    FILE *fout = fopen("xd.out", "w");
    fprintf(fout, "%.10f", rez);
    fclose(fout);
    return 0;
}

/*

Graful construit:

Noi ne construim un graf bipartit format din doua multimi A si B. Noi vrem sa cuplam fiecare nod din multimea A cu un nod din multimea B
Costul unei muchii dintre A si B va fi distanta dintre cele doua puncte pe care le reprezinta.

Algoritmul de cuplaj maxim de cost minim se implementeaza cu ajutorul algoritmului de flux maxim de cost minim

Avem sursa(0) si destinatia(2*n+1) si nodurile interne (cele din multimea A(1...N) si cele din multimea B(N+1...2N))
Intre sursa si fiecare nod din multimea A avem o muchie de capacitate 1 si cost 0
Intre fiecare nod din multimea B si destinatie avem o muchie de capacitate 1 si cost 0
Intre fiecare nod din multimea A si multimea B avem o muchie de capacitate 1 si cost egal cu distanta dintre cele doua puncte

Capacitatile de la ultimul tip de muchii nu este asa de relevant, acesta poate fi infinita, atata timp cat este mai mare decat 1.
Celalalte muchii trebuie sa aiba capacitate neaparat 1

*/