Cod sursa(job #2632945)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 5 iulie 2020 18:25:11
Problema Adapost Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.21 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] , d1[NMAX + 5] , d2[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;
}
void bellmanford()
{
    int u , v , i;
    for(i = 0 ; i <= t ; i ++)
        d1[i] = INF;
    d1[s] = 0;
    memset(viz , 0 , sizeof(viz));
    queue <int> q;
    q.push(s);
    viz[s] = 1;
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        viz[u] = 0;
        for(i = 0 ; i < G[u].size() ; i ++)
        {
            v = G[u][i];
            if(cf[u][v] && d1[v] > d1[u] + cst[u][v])
            {
                d1[v] = d1[u] + cst[u][v];
                if(!viz[v])
                {
                    q.push(v);
                    viz[v] = 1;
                }
            }
        }
    }
}
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] + d1[u] + cst[u][v] - d1[v];
                if(new_cost < d[v])
                {
                    d[v] = new_cost;
                    d2[v] = d2[u] + cst[u][v];
                    p[v] = u;
                    pq.push(path(v , new_cost));
                }
            }
        }
    }
    memcpy(d1 , d2 , sizeof(d2));
    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 += d1[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 = 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 ++)
        {
            mch[++ k] = dist(P[i] , P[j]);
            cst[i][j] = mch[k];
            cst[j][i] = -mch[k];
        }
    sort(mch + 1 , mch + k + 1);
    poz = bs();
    lim = mch[poz];
    for(i = 1 ; i <= n ; i ++)
        for(j = n + 1 ; j <= 2 * n ; j ++)
        {
            double dst = dist(P[i] , P[j]);
            if(dst <= lim)
            {
                G[i].push_back(j);
                G[j].push_back(i);
                cf[i][j] = 1;
            }
        }
    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;
    }
    bellmanford();
    printf("%lf %lf\n" , lim , cmcm());
    return 0;
}