Cod sursa(job #2632958)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 5 iulie 2020 18:56:40
Problema Adapost Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.26 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 800;
const double INF = 2.e9;
struct POINT
{
    double x , y;
    POINT(double tx = 0.0 , double ty = 0.0)
    {
        x = tx;
        y = ty;
    }
};
POINT P[NMAX + 5];
int cf[NMAX + 5][NMAX + 5] , p[NMAX + 5] , n , s , t;
double cst[NMAX + 5][NMAX + 5] , d[NMAX + 5] , lim;
int l[NMAX / 2 + 5] , r[NMAX + 5] , viz[NMAX / 2 + 5];
vector <int> G[NMAX + 5];
vector <pair <double , pair <int , int> > > mch;
double dist(POINT P1 , POINT P2)
{
    return sqrt((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}
int dijkstra()
{
    int u , v , i;
    double cost , new_cost;
    for(i = 0 ; i <= t ; i ++)
        d[i] = INF;
    d[s] = 0;
    priority_queue <pair <double , int> , vector <pair <double , int> > , greater <pair <double , int> > > pq;
    pq.push({0.0 , s});
    while(!pq.empty())
    {
        u = pq.top().second;
        cost = pq.top().first;
        pq.pop();
        if(d[u] < cost)
            continue;
        for(i = 0 ; i < G[u].size() ; i ++)
        {
            v = G[u][i];
            if(cf[u][v])
            {
                new_cost = d[u] + cst[u][v];
                if(new_cost < d[v])
                {
                    d[v] = new_cost;
                    p[v] = u;
                    pq.push({d[v] , v});
                }
            }
        }
    }
    if(d[t] != INF)
        return 1;
    return 0;
}
double cmcm()
{
    double cost = 0.0;
    while(dijkstra())
    {
        int nod , flow;
        flow = INT_MAX;
        for(nod = t ; nod != s ; nod = p[nod])
            flow = min(flow , cf[p[nod]][nod]);
        for(nod = t ; nod != s ; nod = p[nod])
        {
            cf[p[nod]][nod] -= flow;
            cf[nod][p[nod]] += flow;
        }
        cost += d[t] * flow;
    }
    return cost;
}
int alternating_path(int u)
{
    if(viz[u])
        return 0;
    viz[u] = 1;
    for(int v = n + 1 ; v <= 2 * n ; v ++)
        if(cst[u][v] <= lim && !r[v])
        {
            l[u] = v;
            r[v] = u;
            return 1;
        }
    for(int v = n + 1 ; v <= 2 * n ; v ++)
        if(cst[u][v] <= lim && alternating_path(r[v]))
        {
            l[u] = v;
            r[v] = u;
            return 1;
        }
    return 0;
}
int verif()
{
    memset(l , 0 , sizeof(l));
    memset(r , 0 , sizeof(r));
    int cuplaj , gasit , i;
    cuplaj = 0;
    do
    {
        gasit = 0;
        memset(viz , 0 , sizeof(viz));
        for(i = 1 ; i <= n ; i ++)
            if(!l[i] && alternating_path(i))
            {
                gasit = 1;
                cuplaj ++;
            }
    }
    while(gasit);
    return cuplaj == n;
}
int bs()
{
    int st , dr , med , last;
    st = 0;
    dr = mch.size() - 1;
    while(st <= dr)
    {
        med = (st + dr) / 2;
        lim = mch[med].first;
        if(verif())
        {
            last = med;
            dr = med - 1;
        }
        else
            st = med + 1;
    }
    return last;
}
int main()
{
    freopen("adapost.in" , "r" , stdin);
    freopen("adapost.out" , "w" , stdout);
    int i , j , k , poz , u , v;
    double x , y , dst;
    scanf("%d" , &n);
    for(i = 1 ; i <= 2 * n ; i ++)
    {
        scanf("%lf%lf" , &x , &y);
        P[i] = POINT(x , y);
    }
    k = 0;
    for(i = 1 ; i <= n ; i ++)
        for(j = n + 1 ; j <= 2 * n ; j ++)
        {
            dst = dist(P[i] , P[j]);
            mch.push_back({dst , {i , j}});
            cst[i][j] = dst;
            cst[j][i] = -dst;
        }
    sort(mch.begin() , mch.end());
    poz = bs();
    s = 0;
    t = 2 * n + 1;
    for(i = 0 ; i <= poz ; i ++)
    {
        u = mch[i].second.first;
        v = mch[i].second.second;
        G[u].push_back(v);
        G[v].push_back(u);
        cf[u][v] = 1;
    }
    for(i = 1 ; i <= n ; i ++)
    {
        G[s].push_back(i);
        G[i].push_back(s);
        G[i + n].push_back(t);
        G[t].push_back(i + n);
        cf[s][i] = cf[i + n][t] = 1;
    }
    printf("%lf %lf\n" , mch[poz].first , cmcm());
    return 0;
}