Cod sursa(job #1895521)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 28 februarie 2017 00:02:53
Problema Adapost Scor 26
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

ifstream fin("adapost.in");
ofstream fout("adapost.out");

const int inf = 1e9;

#define nmax 805
#define mp make_pair
#define f first
#define s second

priority_queue <pair<double,int>, vector<pair<double,int> >, greater<pair<double,int> > >q;
vector <int> v[nmax];
vector <int> g[nmax];
pair<int,int> pozs[nmax];
pair<int,int> poza[nmax];
double cst[nmax][nmax];
int c[nmax][nmax];
int f[nmax][nmax];
double d[nmax];
int t[nmax];
int r[nmax];
int l[nmax];
int viz[nmax];
long double cost;
int mn,a,b,n;

inline double ab(double x)
{
    if(x<0)
        return -x;
    return x;
}

double dist(pair<int,int> a,pair<int,int> b)
{
    return (double)sqrt(1LL*(a.f-b.f)*(a.f-b.f)+1LL*(a.s-b.s)*(a.s-b.s));
}

bool dijkstra(double mx)
{
    for(int i=1; i<=b; ++i)
        d[i]=inf;
    d[a]=0;
    q.push(mp(0,a));
    while(!q.empty())
    {
        int nod = q.top().s;
        double curr = q.top().f;
        q.pop();
        if(curr!=d[nod] || nod==b)
            continue;
        for(auto it:v[nod])
            if(ab(cst[nod][it])<=mx && (double)d[nod]+cst[nod][it]<d[it] && c[nod][it]>f[nod][it])
            {
                d[it]=d[nod]+cst[nod][it];
                t[it]=nod;
                q.push(mp(d[it],it));
            }
    }
    return d[b]!=inf;
}

void flux(int mx)
{
    cost = 0;

    while(dijkstra(mx))
    {
        int flow = inf;
        for(int i=b; i!=a; i=t[i])
            flow=min(flow,c[t[i]][i]-f[t[i]][i]);
        for(int i=b; i!=a; i=t[i])
        {
            f[t[i]][i]+=flow;
            f[i][t[i]]-=flow;
            cost+=cst[t[i]][i];
        }
    }
}

bool pairup(int x,int mx)
{
    if(viz[x])
        return 0;
    viz[x]=1;
    for(auto it:g[x])
        if(!r[it] && ab(cst[x][it+n])<=(double)mx)
        {
            r[it]=x;
            l[x]=it;
            return 1;
        }
    for(auto it:g[x])
        if(ab(cst[x][it+n])<=(double)mx && pairup(r[it],mx))
        {
            r[it]=x;
            l[x]=it;
            return 1;
        }
    return 0;
}

bool cuplaj(int mx)
{
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
    int ok=1;
    while(ok)
    {
        ok=0;
        memset(viz, 0, sizeof(viz));
        for(int i=1; i<=n; ++i)
            if(!l[i])
                ok|=pairup(i,mx);
    }
    int ans=0;
    for(int i=1; i<=n; ++i)
        if(l[i])
            ++ans;
    return ans==n;
}

void bs()
{
    mn = 10000000;
    int p=1;
    for( ; p<mn; p<<=1);
    for( ; p; p>>=1)
        while(mn-p>0 && cuplaj(mn-p))
            mn-=p;
}

int main()
{
    fin>>n;
    int i,j;
    for(i=1; i<=n; ++i)
    {
        float a,b;
        fin>>a>>b;
        pozs[i]=mp(a*10000,b*10000);
    }
    for(i=1; i<=n; ++i)
    {
        float a,b;
        fin>>a>>b;
        poza[i]=mp(a*10000,b*10000);
    }
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
        {
            g[i].push_back(j);

            c[i][j+n]=1;
            cst[i][j+n]=dist(pozs[i],poza[j]);
            cst[j+n][i]=-cst[i][j+n];
            v[i].push_back(j+n);
            v[j+n].push_back(i);
        }
    a = 0;
    b = 2*n+1;
    for(i=1; i<=n; ++i)
    {
        c[a][i]=1;
        v[a].push_back(i);
    }
    for(i=1; i<=n; ++i)
    {
        c[n+i][b]=1;
        v[n+i].push_back(b);
    }
    bs();
    flux(mn);
    fout<<(double)mn/10000<<' '<<(double)cost/10000;
}