Cod sursa(job #2632940)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 5 iulie 2020 17:50:38
Problema Adapost Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.56 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] , mch[80205] , lim;
int l[NMAX / 2 + 5] , r[NMAX + 5] , viz[NMAX / 2 + 5];
vector <int> G[NMAX + 5];
double dist(POINT P1 , POINT P2)
{
    return sqrt((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}
struct path
{
    int nod;
    double cost;
    path(int x = 0 , double y = 0.0)
    {
        nod = x;
        cost = y;
    }
};
bool operator<(const path& a , const path& b)
{
    return a.cost > b.cost;
}
int dijkstra()
{
    int u , v , i;
    double cost , new_cost;
    for(i = 0 ; i <= t ; i ++)
        d[i] = INF;
    d[s] = 0;
    priority_queue <path> pq;
    pq.push(path(s , 0.0));
    while(!pq.empty())
    {
        u = pq.top().nod;
        cost = pq.top().cost;
        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(path(v , new_cost));
                }
            }
        }
    }
    if(d[t] != INF)
        return 1;
    return 0;
}
int get_flow()
{
    int nod , flow;
    flow = INT_MAX;
    for(nod = t ; nod != s ; nod = p[nod])
        flow = min(flow , cf[p[nod]][nod]);
    return flow;
}
double set_flow(int flow)
{
    for(int nod = t ; nod != s ; nod = p[nod])
    {
        cf[p[nod]][nod] -= flow;
        cf[nod][p[nod]] += flow;
    }
    return d[t] * flow;
}
void init()
{
    int i , j;
    memset(cf , 0 , sizeof(cf));
    for(i = 1 ; i <= n ; i ++)
        for(j = n + 1 ; j <= 2 * n ; j ++)
            if(cst[i][j] <= lim)
                cf[i][j] = 1;
    for(i = 1 ; i <= n ; i ++)
        cf[s][i] = cf[i + n][t] = 1;
}
double cmcm()
{
    double cost = 0.0;
    init();
    while(dijkstra())
        cost += set_flow(get_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 = 1;
    dr = n * n;
    while(st <= dr)
    {
        med = (st + dr) / 2;
        lim = mch[med];
        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;
    double x , y;
    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 ++)
        {
            G[i].push_back(j);
            G[j].push_back(i);
            mch[++ k] = dist(P[i] , P[j]);
            cf[i][j] = 1;
            cst[i][j] = mch[k];
            cst[j][i] = -mch[k];
        }
    s = 0;
    t = 2 * n + 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;
    }
    sort(mch + 1 , mch + k + 1);
    poz = bs();
    lim = mch[poz];
    printf("%lf %lf\n" , lim , cmcm());
    return 0;
}