Cod sursa(job #2932026)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 1 noiembrie 2022 17:26:26
Problema Adapost Scor 27
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.6 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>

using namespace std;

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

const double eps = 1e-6, inf = 1000000;
const int maxN = 805;
int n, m, sursa, dest, l[maxN], r[maxN];
double fake_dist[maxN], real_dist[maxN], dist[maxN], total_cost;
int prv[maxN], max_flow, max_cuplaj;
bool used[maxN];
struct muchie {
    int nxt, flux, cap;
    double cost;
}lm[325005];
vector <int> G[maxN];
struct haha4heap {
    int nod;
    double cost;
    bool operator < (const haha4heap &other) const {
        return cost > other.cost;
    }
};
priority_queue <haha4heap> heap;
queue <int> q;
struct point {
    double x, y;
}v1[405], v2[405];

void create_edges();
double get_dist(int a, int b);
void compute_cuplaj(double val);
bool pairup(int nod, double val);
void compute_flux(double val);
void bellman_ford();
bool dijkstra();

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> v1[i].x >> v1[i].y;
    for(int i = 1; i <= n; i++)
        fin >> v2[i].x >> v2[i].y;
    sursa = 0;
    dest = 2 * n + 1;
    create_edges();
    double st = 0, dr = 1500, ans = 1500;
    while(st + eps <= dr)
    {
        double med = (st + dr) / 2;
        compute_cuplaj(med);
        if(max_cuplaj == n)
        {
            ans = med;
            dr = med;
        }
        else
            st = med;
    }
    compute_flux(ans);
    fout << setprecision(6) << fixed << ans << ' ' << total_cost << '\n';
    return 0;
}


void create_edges()
{
    int k = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            double cst = get_dist(i, j);
            lm[2 * k] = {n + j, 0, 1, cst};
            lm[2 * k + 1] = {i, 0, 0, -cst};
            G[i].push_back(2 * k);
            G[n + j].push_back(2 * k + 1);
            k++;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        lm[2 * k] = {i, 0, 1, 0};
        lm[2 * k + 1] = {sursa, 0, 0, 0};
        G[sursa].push_back(2 * k);
        G[i].push_back(2 * k + 1);
        k++;
    }
    for(int i = 1; i <= n; i++)
    {
        lm[2 * k] = {dest, 0, 1, 0};
        lm[2 * k + 1] = {n + i, 0, 0, 0};
        G[n + i].push_back(2 * k);
        G[dest].push_back(2 * k + 1);
        k++;
    }
}

double get_dist(int a, int b)
{
    double deltax = v1[a].x - v2[b].x, deltay = v1[a].y - v2[b].y;
    double d = sqrt(deltax * deltax + deltay * deltay);
    return d;
}

void compute_cuplaj(double val)
{
    bool changed = 1;
    while(changed)
    {
        changed = 0;
        for(int i = 1; i <= n; i++)
            used[i] = 0;
        for(int i = 1; i <= n; i++)
            if(!l[i])
                changed |= pairup(i, val);
    }
    max_cuplaj = 0;
    for(int i = 1; i <= n; i++)
        if(l[i])
            max_cuplaj++;
    for(int i = 1; i <= n; i++)
    {
        l[i] = 0;
        r[n + i] = 0;
    }
}

bool pairup(int nod, double val)
{
    if(used[nod])
        return 0;
    used[nod] = 1;
    for(int ind : G[nod])
    {
        muchie aux = lm[ind];
        if(!r[aux.nxt] && aux.nxt != 0 && aux.cost <= val)
        {
            l[nod] = aux.nxt;
            r[aux.nxt] = nod;
            return 1;
        }
    }
    for(int ind : G[nod])
    {
        muchie aux = lm[ind];
        if(aux.nxt == 0 || aux.cost > val)
            continue;
        if(pairup(r[aux.nxt], val))
        {
            l[nod] = aux.nxt;
            r[aux.nxt] = nod;
            return 1;
        }
    }
    return 0;
}

void compute_flux(double val)
{
    bellman_ford();
    while(dijkstra())
    {
        int min_flow = inf;
        for(int x = dest; x != sursa; x = lm[prv[x] ^ 1].nxt)
            min_flow = min(min_flow, lm[prv[x]].cap - lm[prv[x]].flux);
        for(int x = dest; x != sursa; x = lm[prv[x] ^ 1].nxt)
        {
            lm[prv[x]].flux += min_flow;
            lm[prv[x] ^ 1].flux -= min_flow;
        }
        total_cost += 1.0 *  min_flow * dist[dest];
        max_flow += min_flow;
    }
}

void bellman_ford()
{
    for(int i = sursa; i <= dest; i++)
        dist[i] = inf;
    dist[sursa] = 0;
    q.push(sursa);
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();
        for(int ind : G[curr])
        {
            muchie aux = lm[ind];
            if(aux.cap == 0 || dist[curr] + aux.cost >= dist[aux.nxt])
                continue;
            dist[aux.nxt] = dist[curr] + aux.cost;
            q.push(aux.nxt);
        }
    }
}

bool dijkstra()
{
    for(int i = sursa; i <= dest; i++)
    {
        fake_dist[i] = inf;
        real_dist[i] = dist[i];
        used[i] = 0;
    }
    while(!heap.empty())
        heap.pop();
    fake_dist[sursa] = 0;
    dist[sursa] = 0;
    heap.push({sursa, 0});
    while(!heap.empty())
    {
        int curr = heap.top().nod;
        heap.pop();
        if(used[curr])
            continue;
        used[curr] = 1;
        for(int ind : G[curr])
        {
            muchie aux = lm[ind];
            if(aux.flux < aux.cap && fake_dist[curr] + aux.cost + real_dist[curr] - real_dist[aux.nxt] < fake_dist[aux.nxt])
            {
                prv[aux.nxt] = ind;
                fake_dist[aux.nxt] = fake_dist[curr] + aux.cost + real_dist[curr] - real_dist[aux.nxt];
                dist[aux.nxt] = dist[curr] + aux.cost;
                heap.push({aux.nxt, fake_dist[aux.nxt]});
            }
        }
    }
    if(fake_dist[dest] == inf)
        return 0;
    return 1;
}