Cod sursa(job #2276518)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 4 noiembrie 2018 20:10:32
Problema Adapost Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.91 kb
#include <bits/stdc++.h>

const double eps=1e-13;
const int oo=1e9;
const int N=410;

using namespace std;

//ifstream f("adapost.in");
//ofstream g("adapost.out");
FILE *f = fopen("adapost.in","r");
FILE *g = fopen("adapost.out","w");

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[it]-dist[x])>eps))
            {
//                cout<<"ye: "<<it<<'\n';
                new_d[it]=new_d[x]+cost[x][it]+dist[it]-dist[x];
                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()
{
//    f>>n;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
//        f>>sold[i].first>>sold[i].second;
        fscanf(f,"%lf %lf",&sold[i].first,&sold[i].second);
    for(i=1;i<=n;i++)
//        f>>home[i].first>>home[i].second;
        fscanf(f,"%lf %lf",&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';

    fprintf(g,"%.6f ",u[lo].first);
 //   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(););
    fprintf(g,"%.6f ",flow);
//    g<<fixed<<setprecision(5)<<flow;
    fclose(f);
    fclose(g);
    return 0;
}