Cod sursa(job #2276644)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 5 noiembrie 2018 00:54:51
Problema Adapost Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.96 kb
#include <bits/stdc++.h>



const double eps=1e-5;

const int oo=1e9;

const int N=410;



using namespace std;



int n,i,j,mi,lo,hi,poz[N][N],cap[2*N][2*N];

pair<double,double> sold[N],home[N];

vector<pair<double,pair<int,int> > > u;

double flow,cost[2*N][2*N],dist[2*N];

vector<int> v[2*N],fren[N];

bitset<N> viz;

int S[N],D[N];



bool grow(int poz)

{

    if(viz[poz])return 0;

    viz[poz]=1;

    for(auto it:fren[poz])

        if(!S[it])

        {

            S[it]=poz;

            D[poz]=it;

            return 1;

        }

    for(auto it:fren[poz])

        if(grow(S[it]))

        {

            S[it]=poz;

            D[poz]=it;

            return 1;

        }

    return 0;

}



bool bipart(int mi)

{

    for(int i=1;i<=n;i++)

        S[i]=D[i]=0;

    for(int i=1;i<=n;i++)

    {

        fren[i].resize(0);

        for(j=1;j<=n;j++)

            if(poz[i][j]<=mi)

                fren[i].push_back(j);

    }

    int meci=0;

    for(bool ok=1;ok;)

    {

        ok=0;viz.reset();

        for(int i=1;i<=n;i++)

            if((!D[i])&&grow(i))

            {

                ok=1;

                meci++;

            }

    }

    return (meci==n);

}



void bell()

{

    queue<int> Q;

    bitset<2*N> in;in.reset();

    for(i=0;i<=2*n+1;i++)

        dist[i]=oo;

    dist[0]=0;Q.push(0);in[0]=1;

    while(Q.size())

    {

        int x=Q.front();

        Q.pop();in[x]=0;

        for(auto it:v[x])

            if(cap[x][it]&&(dist[it]-(dist[x]+cost[x][it])>eps))

            {

                dist[it]=dist[x]+cost[x][it];

                if(!in[it])

                    Q.push(it);

                in[it]=1;

            }

    }

}



bool dij()

{

    priority_queue<pair<double,int> > Q;

    int tata[2*N];

    double new_d[2*N],real_d[2*N];

    for(i=0;i<=2*n+1;i++)

        real_d[i]=new_d[i]=tata[i]=oo;

    real_d[0]=new_d[0]=tata[0]=0;

    Q.push({0,0});

    while(Q.size())

    {

        int           x= Q.top().second;

        double cst=-Q.top().first;

        Q.pop();

//        cout<<"JEF: "<<x<<'\n';

        if(cst!=new_d[x])

            continue;

        for(auto it:v[x])

            if(cap[x][it]&&(new_d[it]-(new_d[x]+cost[x][it]+dist[x]-dist[it])>eps))

            {

//                cout<<"ye: "<<it<<'\n';

                new_d[it]=new_d[x]+cost[x][it]+dist[x]-dist[it];

                Q.push({-new_d[it],it});

                real_d[it]=real_d[x]+cost[x][it];

                tata[it]=x;

            }

//            else

//                cout<<"na: "<<it<<'\n';

    }

//    for(i=0;i<=2*n+1;i++)

//        cout<<dist[i]<<' ';

//    cout<<'\n';

    for(i=0;i<=2*n+1;i++)

        dist[i]=real_d[i];

//    for(i=0;i<=2*n+1;i++)

//        cout<<dist[i]<<' ';

//    cout<<'\n';

//    cout<<'\n';

    if(dist[2*n+1]==oo)

        return 0;

    int flux=oo;

    for(int nod=2*n+1;nod;nod=tata[nod])

        flux=min(flux,cap[tata[nod]][nod]);

    for(int nod=2*n+1;nod;nod=tata[nod])

    {

        cap[tata[nod]][nod]-=flux;

        cap[nod][tata[nod]]+=flux;

    }

    flow+=dist[2*n+1]*(double)flux;

    return 1;

}



int main()

{

    ifstream f("adapost.in");

    ofstream g("adapost.out");

    f>>n;

    for(i=1;i<=n;i++)

        f>>sold[i].first>>sold[i].second;

    for(i=1;i<=n;i++)

        f>>home[i].first>>home[i].second;

    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

        {

            cost[i][j+n]=sqrt((sold[i].first-home[j].first)*(sold[i].first-home[j].first)+

                              (sold[i].second-home[j].second)*(sold[i].second-home[j].second));

            cost[j+n][i]=-cost[i][j+n];

            u.push_back({cost[i][j+n],{i,j}});

            v[i].push_back(j+n);

            v[j+n].push_back(i);

        }

    u.push_back({0,{0,0}});

    sort(u.begin(),u.end());

    for(i=1;i<=n*n;i++)

        poz[u[i].second.first][u[i].second.second]=i;

    lo=1,hi=n*n;

    while(lo<hi)

    {

        mi=(lo+hi)/2;

        if(bipart(mi))

            hi=mi;

        else

            lo=mi+1;

    }

//    for(i=1;i<=n*n;i++)

//        cout<<bipart(i)<<' ';cout<<'\n';

//    for(i=1;i<=n*n;i++)

//        cout<<u[i].second.first<<' '<<u[i].second.second<<' '<<u[i].first<<'\n';

//    cout<<lo<<'\n';

    g<<fixed<<setprecision(5)<<u[lo].first<<' ';

    for(i=1;i<=lo;i++)

        cap[u[i].second.first][u[i].second.second+n]=N;

    for(i=1;i<=n;i++)

    {

        cap[0][i]=1;

        v[0].push_back(i);

    }

    for(i=n+1;i<=2*n;i++)

    {

        cap[i][2*n+1]=1;

        v[i].push_back(2*n+1);

    }

    bell();

    for(;dij(););

    g<<fixed<<setprecision(5)<<flow;

    return 0;

}