Cod sursa(job #2937973)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 11 noiembrie 2022 15:01:00
Problema Adapost Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.38 kb
///hai si cu suta
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>

using namespace std;

ifstream in ("adapost.in");
ofstream out ("adapost.out");

const int max_size = 8e2 + 9;
const double INF = 1e9 + 1;

struct str{
    int nod;
    double val;
    bool operator < (const str &aux) const
    {
        return val > aux.val;
    }
};

#define pdd pair <double, double>

double cap[max_size][max_size], cost[max_size][max_size], d[max_size][max_size], dist[max_size], pr[max_size], aux[max_size];
int t[max_size], dr[max_size], st[max_size], n;
pdd sld[max_size], adp[max_size];
bitset <max_size> viz;
vector <int> mc[max_size];
queue <int> q;

void bf ()
{
    for (int i = 1; i <= 2 * n + 2; i++)
    {
        aux[i] = INF;
        viz[i] = 0;
    }
    aux[1] = 0;
    q.push(1);
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        viz[nod] = 0;
        for (auto f : mc[nod])
        {
            if (aux[nod] + cost[nod][f] < aux[f] && cap[nod][f] > 0)
            {
                aux[f] = aux[nod] + cost[nod][f];
                if (viz[f] == 0)
                {
                    viz[f] = 1;
                    q.push(f);
                }
            }
        }
    }
}

bool bfs ()
{
    for (int i = 1; i <= 2 * n + 2; i++)
    {
        dist[i] = INF;
        viz[i] = 0;
    }
    dist[1] = 0;
    viz[1] = 1;
    q.push(1);
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        viz[nod] = 0;
        if (nod == 2 * n + 2)
            continue;
        for (auto f : mc[nod])
        {
            if (cost[nod][f] > 0 && dist[nod] + cap[nod][f] < dist[f])
            {
                dist[f] = dist[nod] + cap[nod][f];
                t[f] = nod;
                if (!viz[f])
                {
                    viz[f] = 1;
                    q.push(f);
                }
            }
        }
    }
    return (dist[2 * n + 2] != INF);
}

bool pairup (int nod)
{
    if (viz[nod])
    {
        return false;
    }
    viz[nod] = 1;
    for (auto f : mc[nod])
    {
        if (dr[f] == 0)
        {
            st[nod] = f;
            dr[f] = nod;
            return true;
        }
    }
    for (auto f : mc[nod])
    {
        if (pairup(dr[f]))
        {
            st[nod] = f;
            dr[f] = nod;
            return true;
        }
    }
    return false;
}

bool verif (double x)
{
    for (int i = 1; i <= 2 * n + 2; i++)
    {
        mc[i].clear();
    }
    for (int i = 1; i <= n; i++)
    {
        st[i + 1] = 0;
        st[i + n + 1] = 0;
        dr[i + 1] = 0;
        dr[i + n + 1] = 0;
        for (int j = 1; j <= n; j++)
        {
            if (d[i][j] <= x)
            {
                mc[i + 1].push_back(n + j + 1);
                mc[n + j + 1].push_back(i + 1);
            }
        }
    }
    bool ok = false;
    while (1)
    {
        for (int i = 1; i <= 2 * n + 2; i++)
        {
            viz[i] = 0;
        }
        ok = false;
        for (int i = 2; i <= n + 1; i++)
        {
            if (!st[i])
            {
                ok |= pairup(i);
            }
        }
        if (!ok)
        {
            break;
        }
    }
    int ct = 0;
    for (int i = 2; i <= n + 1; i++)
    {
        if (st[i] > 0)
        {
            ct++;
        }
    }
    return (ct == n);
}

int main ()
{
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> sld[i].first >> sld[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        in >> adp[i].first >> adp[i].second;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            d[i][j] = sqrt((sld[i].first - adp[j].first) * (sld[i].first - adp[j].first) + (sld[i].second - adp[j].second) * (sld[i].second - adp[j].second));
        }
    }
    double l = 0, r = 2000;
    while (r - l > 0.0001)
    {
        double m = (l + r) / 2;
        if (verif(m))
        {
            r = m;
        }
        else
        {
            l = m;
        }
    }
    out << fixed << setprecision(5) << l << " ";
    for (int i = 1; i <= 2 * n + 2; i++)
    {
        mc[i].clear();
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (d[i][j] <= l)
            {
                mc[1].push_back(i + 1);
                mc[i + 1].push_back(1);
                mc[i + 1].push_back(j + n + 1);
                mc[j + n + 1].push_back(i + 1);
                mc[j + n + 1].push_back(2 * n + 2);
                mc[2 * n + 2].push_back(j + n + 1);
                cost[1][i + 1] = 1;
                cost[i + 1][j + n + 1] = 1;
                cost[j + n + 1][2 * n + 2] = 1;
                cap[i + 1][j + n + 1] = d[i][j];
                cap[j + n + 1][i + 1] = -d[i][j];
            }
        }
    }
    bf();
    double ans = 0;
    while (bfs())
    {
        int nod = 2 * n + 2;
        ans += dist[2 * n + 2];
        while (nod != 1)
        {
            cost[t[nod]][nod]--;
            cost[nod][t[nod]]++;
            nod = t[nod];
        }
    }
    out << fixed << setprecision(5) << ans;
    in.close();
    out.close();
    return 0;
}