Cod sursa(job #1895425)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 27 februarie 2017 22:39:30
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 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];
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];
double ans,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((a.f-b.f)*(a.f-b.f)+(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])
            continue;
        for(auto it:v[nod])
            if(ab(cst[nod][it])<=mx && 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;
}

int flux(int mx)
{
    memset(f, 0, sizeof(f));
    cost = 0;
    int maxflow = 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+=(double)flow*cst[t[i]][i];
        }
        maxflow+=flow;
    }
    return maxflow;
}

void bs()
{
    mn = 100000000;
    int p=1;
    for( ; p<mn; p<<=1);
    for( ; p; p>>=1)
        if(mn-p>0 && flux(mn-p)==n)
        {
            mn-=p;
            ans=cost;
        }
}

int main()
{
    fin>>n;
    int i,j;
    for(i=1; i<=n; ++i)
    {
        float a,b;
        fin>>a>>b;
        pozs[i]=mp(a*1000,b*1000);
    }
    for(i=1; i<=n; ++i)
    {
        float a,b;
        fin>>a>>b;
        poza[i]=mp(a*1000,b*1000);
    }
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++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();
    fout<<(double)mn/1000<<' '<<(double)ans/1000;
}