Cod sursa(job #3032949)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 23 martie 2023 10:17:28
Problema Adapost Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <fstream>
#define D double
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#define esp 1e-3
#include <iomanip>
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
int n,m,st,dr;
const int N=805;
struct pct
{
    D x,y;
}v[N],r[N];
struct cr
{
    int x;
    D dt;
};
vector<cr>a[N];
D get_dist(pct A,pct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int flux[N][N];
D d[N][N];
D dist[N];
bool viz[N];
int dad[N];
D ford(int st,int dr,D MIJ)
{
    for(int i=st;i<=dr;i++)
    {
        dist[i]=1e9;
        dad[i]=0;
        viz[i]=false;
    }
    queue<int>q;
    dist[st]=0;
    q.push(st);
    viz[st]=true;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        viz[nod]=false;
        for(auto x: a[nod])
        {
            if(x.dt>MIJ)
                break;
            if(dist[x.x]>dist[nod]+x.dt&&flux[nod][x.x]>0)
            {
                dist[x.x]=dist[nod]+x.dt;
                dad[x.x]=nod;
                if(viz[x.x]==false)
                {
                    viz[x.x]=true;
                    q.push(x.x);
                }
            }
        }
    }
    return dist[dr];
}
D get_flux(D lat)
{
    D vall=0;
    while(true)
    {
        D sol=ford(st,dr,lat);
        if(sol==1e9)
            break;
        for(int i=dr;i!=st;i=dad[i])
        {
            flux[dad[i]][i]--;
            flux[i][dad[i]]++;
        }
        vall=vall+sol;
    }

    for(int i=1;i<=n;i++)
        if(flux[st][i]==1)
            return 2e9;
    return vall;
}
void reset()
{
    for(int i=1;i<=n;i++)
        flux[st][i]=1,flux[i][st]=0;
    for(int i=1;i<=n;i++)
        flux[dr][i+n]=0,flux[i+n][dr]=1;
    for(int i=1;i<=n;i++)
        for(int j=n+1;j<=2*n;j++)
            flux[i][j]=1,flux[j][i]=0;
}
bool cmp(cr X,cr Y)
{
    return X.dt<Y.dt;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    for(int i=1;i<=n;i++)
        f>>r[i].x>>r[i].y;
    st=0;
    dr=2*n+1;
    ///muchie st - i,  i+n dr
    for(int i=1;i<=n;i++)
    {
        a[st].push_back({i,0});
        a[i+n].push_back({dr,0});
        a[dr].push_back({i+n,0});
        a[i].push_back({st,0});
        flux[st][i]=1;
        flux[i+n][dr]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {

            flux[i][j+n]=1;
            D dd=get_dist(v[i],r[j]);
            a[i].push_back({j+n,dd});
            a[j+n].push_back({i,-dd});
        }
    for(int i=1;i<=n;i++)
        sort(a[i].begin(),a[i].end(),cmp);
    D st=0,dr=4000;
    D RE;
    while(dr-st>esp)
    {
        reset();
        D mj=(st+dr)/2;
        D soll=get_flux(mj);
        if(soll<1e9)
            RE=soll,dr=mj;
        else
            st=mj;
    }
    g<<fixed<<setprecision(6)<<dr<<" ";
    g<<fixed<<setprecision(6)<<RE;
    return 0;
}