Cod sursa(job #676174)

Utilizator darrenRares Buhai darren Data 8 februarie 2012 19:59:37
Problema Adapost Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.23 kb
/*
Sursa copiata pentru a testa limita de timp a problemei. 
*/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define maxn 810
#define inf 1000000000
#define maxq 640000

int n, i, j, k, tot, ok;
pair<double, double> s[maxn], a[maxn];
double sol, ctot, sf, cost[maxn][maxn], dist[maxn];
int c[maxn][maxn], f[maxn][maxn], t[maxn], fol[maxn], q[maxn*maxn];
vector<int> v[maxn];
int cuplaj[maxn], cuplat[maxn];
struct fcomp
{
    bool operator() (const int &a, const int &b)
    {
        return dist[a]>dist[b];
    }
};
priority_queue <int,vector<int>,fcomp> qq;
double distanta(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void build_graph(double mx)
{
    memset(f, 0, sizeof(f));
    memset(c, 0, sizeof(c));
    for(int i=0; i<=2*n+1; ++i)
        v[i].clear();

    for(int i=1; i<=n; ++i)
    {
        c[0][i]=c[i+n][n*2+1]=1;
        v[0].push_back(i);
        v[i].push_back(0);
        v[i+n].push_back(n*2+1);
        v[n*2+1].push_back(i+n);

        for(int j=1; j<=n; ++j)
            if(!(cost[i][j+n]>mx))
            {
                v[i].push_back(j+n);
                v[j+n].push_back(i);
                c[i][j+n]=1;
            }
    }
}

void build_cuplaj(double mx)
{
    for(int i=1; i<=n; ++i)
        v[i].clear();

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            if(!(cost[i][j+n]>mx))
                v[i].push_back(j);
}

int flux()
{
    memset(fol, 0, sizeof(fol));

    int nod, fiu, qr=1;
    qq.push(0);

    dist[i]=0;
    fol[0]=1;
    for(int i=1; i<=2*n+1; ++i)
        dist[i]=inf;

    while(!qq.empty())
    {
        nod=qq.top();
        qq.pop();
        fol[nod]=0;
        for(vector<int> :: iterator it=v[nod].begin(); it!=v[nod].end(); ++it)
        {
            fiu=*it;
            if(c[nod][fiu]>f[nod][fiu] && dist[nod]+cost[nod][fiu]<dist[fiu])
            {
                t[fiu]=nod;
                dist[fiu]=dist[nod]+cost[nod][fiu];
                if(fol[fiu]==0)
                {
                    fol[fiu]=1;
                    qq.push(fiu);
                }
            }
        }
    }

    if(dist[2*n+1]==inf)
        return 0;

    nod=2*n+1;
    while(nod)
    {
        ++f[t[nod]][nod];
        --f[nod][t[nod]];
        nod=t[nod];
    }

    ++tot;
    ctot+=dist[2*n+1];

    return 1;
}

int cupleaza(int nod)
{
    int vecin;

    if(fol[nod])
        return 0;

    fol[nod]=1;

    for(int i=0; i<v[nod].size(); ++i)
    {
        vecin=v[nod][i];
        if(!cuplaj[vecin])
        {
            cuplat[nod]=1;
            cuplaj[vecin]=nod;
            return 1;
        }
    }

    for(int i=0; i<v[nod].size(); ++i)
    {
        vecin=v[nod][i];
        if(cuplaj[vecin]!=nod)
        if(cupleaza(cuplaj[vecin]))
        {
            cuplat[nod]=1;
            cuplaj[vecin]=nod;
            return 1;
        }
    }
    return 0;
}


int main()
{
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%lf%lf", &s[i].first, &s[i].second);
    for(int i=1; i<=n; ++i)
        scanf("%lf%lf", &a[i].first, &a[i].second);

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
        {
            cost[i][j+n]=distanta(s[i].first, s[i].second, a[j].first, a[j].second);
            cost[j+n][i]=-cost[i][j+n];
        }

    double med, left=0, right=1500;

    for(int pas=1; pas<=25; ++pas)
    {
        med=(left+right)/2;

        build_cuplaj(med);

        tot=0;
        ctot=0;

        ok=1;
        memset(cuplat, 0, sizeof(cuplat));
        memset(cuplaj, 0, sizeof(cuplaj));
        while(ok)
        {
            ok=0;
            memset(fol, 0, sizeof(fol));
            for(int i=1; i<=n; ++i)
                if(!cuplat[i])
                    if(cupleaza(i))
                    {
                        ok=1;
                        ++tot;
                    }
        }

        if(tot==n)
        {
            sol=med;
            sf=ctot;
            right=med;
        }
        else
            left=med;
    }

    build_graph(sol);

    tot=0;
    ctot=0;

    while(flux());

    printf("%.5lf %.5lf\n", sol, ctot);

    return 0;
}