Cod sursa(job #2276350)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 4 noiembrie 2018 16:59:30
Problema Adapost Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>

const long double eps=1e-5;
const int oo=1e9;

using namespace std;

ifstream f("adapost.in");
ofstream g("adapost.out");

int n,i,j,flow,cap[410][410];
long double ans,lo,hi,x[410],y[410],adx[410],ady[410],cost[410][410];
vector<int> v[1010];

bool bell()
{
    queue<int> Q;
    long double dist[410];int tata[410];
    bitset<410> in;in.reset();
    for(i=0;i<=2*n+1;i++)
        dist[i]=oo,tata[i]=-1;
    dist[0]=0;Q.push(0);
    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]))
            {
                dist[it]=dist[x]+cost[x][it];
                if(!in[it])
                    Q.push(it);
                in[it]=0;
                tata[it]=x;
            }
    }
    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+=flux;
    ans+=dist[2*n+1]*(long double)flux;
    return 1;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>x[i]>>y[i];
    for(i=1;i<=n;i++)
        f>>adx[i]>>ady[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            v[i].push_back(n+j);
            v[n+j].push_back(i);
            cost[i][n+j]=sqrt((x[i]-adx[j])*(x[i]-adx[j])+(y[i]-ady[j])*(y[i]-ady[j]));
            cost[n+j][i]=-cost[i][n+j];
        }
    lo=0,hi=2000;
    for(i=1;i<=n;i++)
        v[0].push_back(i);
    for(j=n+1;j<=2*n;j++)
        v[j].push_back(2*n+1);
    while(hi-lo>eps)
    {
        long double mi=(lo+hi)/2;
        for(i=0;i<=2*n+1;i++)
            for(j=0;j<=2*n+1;j++)
                cap[i][j]=0;
        for(i=1;i<=n;i++)
            cap[0][i]=1;
        for(j=n+1;j<=2*n;j++)
            cap[j][2*n+1]=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(mi-cost[i][n+j]>eps)
                    cap[i][n+j]=oo;
        ans=0;flow=0;
        for(;bell(););
        //cout<<mi<<' '<<flow<<' '<<ans<<'\n';
        if(flow==n)
            hi=mi;
        else
            lo=mi;
    }
    for(i=0;i<=2*n+1;i++)
        for(j=0;j<=2*n+1;j++)
            cap[i][j]=0;
    for(i=1;i<=n;i++)
        cap[0][i]=1;
    for(j=n+1;j<=2*n;j++)
        cap[j][2*n+1]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(hi-cost[i][n+j]>eps)
                cap[i][n+j]=oo;
    ans=0;
    for(;bell(););
    g<<fixed<<setprecision(4)<<hi<<' '<<ans;
    return 0;
}