Cod sursa(job #2715250)

Utilizator adiaioanaAdia R. adiaioana Data 3 martie 2021 12:59:11
Problema Adapost Scor 14
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.16 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
ifstream cin("adapost.in");
ofstream cout("adapost.out");
int N,S,D,  ant[840];
short fl[20][840][840];
double Cst[840][840];
LL inf=2000000001;
queue <int> Q;
vector <pair<double, pair<int,int> > > dvec;
double old_d[840],real_d[840], d[840],aux[840];
int viz[840];

vector <int> G[840];
priority_queue <pair<double,int>, vector<pair<double,int> >, greater<pair<double,int> > > pq;
pair <double,double> soldat[440],adapost[440];
double dist(pair<double,double> A,pair<double,double> B)
{
    return sqrt((A.first-B.first)*(A.first-B.first)+
                (A.second-B.second)*(A.second-B.second));
}
LL Fm;
double Fcst;

void bellmanford();
bool djikstra(int ind,double dmax);
int main()
{
    cin>>N;
    S=0; D=2*N+1;
    for(int i=1; i<=N; ++i)
    {
        cin>>soldat[i].first>>soldat[i].second;
        G[S].push_back(i);
        G[i].push_back(S);
        for(int lg=0; lg<20; ++lg)
        fl[lg][S][i]=1;
    }

    for(int i=1; i<=N; ++i)
    {
        cin>>adapost[i].first>>adapost[i].second;
        G[D].push_back(i+N);
        G[i+N].push_back(D);
        for(int lg=0; lg<20; ++lg)
        fl[lg][i+N][D]=1;
    }

    double dbl;
    for(int i=1; i<=N; ++i)
        for(int j=1; j<=N; ++j)
        {
            for(int lg=0; lg<20; ++lg)
                fl[lg][i][j+N]=1;
            G[i].push_back(j+N);
            G[j+N].push_back(i);
            dbl=dist(soldat[i],adapost[j]);
            dvec.push_back({dbl,{i,j}});
            Cst[i][j+N]=dbl;
            Cst[j+N][i]=-Cst[i][j+N];
        }

    sort(dvec.begin(),dvec.end());
    bellmanford();
    int st,dr,mij;
    double sol,sol2;
    int k=-1;
    st=0; dr=dvec.size()-1; mij=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        Fm=0; Fcst=(double) 0;
        k++;
        for(int i=0; i<=D; ++i)
            old_d[i]=aux[i];
        while(djikstra(k,dvec[mij].first));
        if(Fm==N)
        {
            sol=dvec[mij].first; dr=mij-1;
            sol2=((double)Fcst);
        }
        else st=mij+1;
    }
    cout<<setprecision(6)<<sol<<' ';
    cout<<setprecision(6)<<sol2<<'\n';
    return 0;
}

void bellmanford()
{
    int nod;
    double new_d;
    for(int i=0; i<=D; ++i)
        aux[i]=inf;
    viz[S]=1; aux[S]=0;
    Q.push(S);
    while(!Q.empty())
    {
        nod=Q.front(); Q.pop(); viz[nod]=0;
        if(nod==D)
            continue;
        for(auto nn:G[nod])
            if(fl[0][nod][nn])
            {
                new_d=aux[nod]+Cst[nod][nn];
                if(new_d<aux[nn])
                {
                    aux[nn]=new_d;
                    if(!viz[nn])
                    {
                        viz[nn]=1;
                        Q.push(nn);
                    }
                }
            }
    }
}

bool djikstra(int ind,double dmax)
{
    int nod; double cost, new_d;
    for(int i=0; i<=D; ++i)
        d[i]=inf, ant[i]=i;
    d[S]=real_d[S]=0;
    pq.push({0,S});
    while(!pq.empty())
    {
        nod=pq.top().second;
        cost=pq.top().first;
        pq.pop();
        if(d[nod]!=cost)
            continue;
        for(auto nn:G[nod])
            if(fl[ind][nod][nn] && Cst[nod][nn] <=dmax)
            {
                new_d=old_d[nod]-old_d[nn]+Cst[nod][nn]+d[nod];
                if(new_d<d[nn])
                {
                    d[nn]=new_d;
                    real_d[nn]=real_d[nod]+Cst[nod][nn];
                    ant[nn]=nod;
                    pq.push({d[nn],nn});
                }
            }
    }
    if(d[D]==inf)
        return 0;
    for(nod=0; nod<=D; ++nod) old_d[nod]=real_d[nod];
    LL Fmin=inf;
    double total=0;
    for(nod=D; nod!=S; nod=ant[nod])
    {
        Fmin=min(Fmin, 1ll*fl[ind][ant[nod]][nod]);
        total=total+(double)Cst[ant[nod]][nod];
    }
    Fm+=Fmin;
    Fcst=Fcst+(double)total;
    for(nod=D; nod!=S; nod=ant[nod])
    {
        fl[ind][ant[nod]][nod]-=Fmin;
        fl[ind][nod][ant[nod]]+=Fmin;
    }
    return 1;
}