Cod sursa(job #2715239)

Utilizator adiaioanaAdia R. adiaioana Data 3 martie 2021 12:44:56
Problema Adapost Scor 12
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.93 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#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[32][840][840];
LL Cst[840][840];
LL inf=2000000001;
queue <int> Q;
LL old_d[840],real_d[840], d[840],aux[840];
int viz[840];
vector <int> G[840];
priority_queue <pair<LL,int>, vector<pair<LL,int> >, greater<pair<LL,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,Fcst;

void bellmanford();
bool djikstra(int ind,LL 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<32; ++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<32; ++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<32; ++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])*1000000;
            Cst[i][j+N]=(LL)dbl;
            Cst[j+N][i]=-Cst[i][j+N];
        }

    bellmanford();
    LL st,dr,mij,sol=inf,sol2=inf;
    int k=-1;
    st=0; dr=inf; mij=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        Fm=0; Fcst=0;
        k++;
        for(int i=0; i<=D; ++i)
            old_d[i]=aux[i];
        while(djikstra(k,mij));
        if(Fm==N)
        {
            sol=mij; dr=mij-1; sol2=Fcst;
        }
        else st=mij+1;
    }
    double dbl2;
    dbl=(double)sol/1000000;
    dbl2=(double)sol2/1000000;
    cout<<setprecision(6)<<dbl<<' '<<dbl2<<'\n';
    return 0;
}

void bellmanford()
{
    int nod;
    LL 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,LL dmax)
{
    int nod; LL 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,total=0;
    for(nod=D; nod!=S; nod=ant[nod])
    {
        Fmin=min(Fmin, 1ll*fl[ind][ant[nod]][nod]);
        total+=Cst[ant[nod]][nod];
    }
    Fm+=Fmin;
    Fcst+=total;
    for(nod=D; nod!=S; nod=ant[nod])
    {
        fl[ind][ant[nod]][nod]-=Fmin;
        fl[ind][nod][ant[nod]]+=Fmin;
    }
    return 1;
}