Cod sursa(job #17063)

Utilizator victorsbVictor Rusu victorsb Data 14 februarie 2007 20:10:01
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 4 kb
#include <cstdio>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

#define Nmax 405
#define x first
#define y second
#define pb push_back
#define sz(a) int((a).size())

int n;
int v[Nmax], dest[Nmax], p[Nmax], cap[2*Nmax][2*Nmax], cd[Nmax * Nmax * 100];
pair<double, double> s[Nmax], a[Nmax];
double dist[Nmax*Nmax], c[2*Nmax][2*Nmax], d[Nmax];
vector<int> lv[Nmax];
int tip[Nmax*Nmax * 100];

void citire()
{
    int i;
    scanf("%d\n", &n);
    for (i=1; i<=n; ++i)
        scanf("%lf %lf\n", &s[i].x, &s[i].y);
    for (i=1; i<=n; ++i)
        scanf("%lf %lf\n", &a[i].x, &a[i].y);
}

double dst(int p1, int p2)
{
    return sqrt((s[p1].x - a[p2].x) * (s[p1].x - a[p2].x) + (s[p1].y - a[p2].y) * (s[p1].y - a[p2].y));
}

int cupleaza(int nod)
{
    int i;
    v[nod] = 1;
    for (i=0; i<sz(lv[nod]); ++i)
        if (!dest[lv[nod][i]])
        {
            dest[lv[nod][i]] = nod;
            p[nod] = lv[nod][i];
            return 1;
        }
    for (i=0; i<sz(lv[nod]); ++i)
        if (!v[dest[lv[nod][i]]])
            if (cupleaza(dest[lv[nod][i]]))
            {
                dest[lv[nod][i]] = nod;
                p[nod] = lv[nod][i];
                return 1;
            }
    return 0;
}

int merge(double dist)
{
    int i, j, flux = 0, ok;
    memset(dest, 0, sizeof(dest));
    memset(p, 0, sizeof(p));
    for (i=1; i<=n; ++i)
    {
        lv[i].clear();
        for (j=1; j<=n; ++j)
            if (c[i][j] <= dist)
                lv[i].pb(j);
    }
    ok = 1;
    while (ok)
    {
        ok = 0;
        memset(v, 0, sizeof(v));
        for (i=1; i<=n; ++i)
            if (!p[i])
                if (cupleaza(i))
                {
                    ++flux;
                    ok = 1;
                }
    }
    if (flux == n)
        return 1;
    return 0;
}

int bellman_ford()
{
    int st = 0, dr = 1, nod, i;
    cd[dr] = 0;
    for (i=0; i<=2*n+1; ++i)
        d[i] = 1000000000;
    d[0] = 0;
    memset(p, -1, sizeof(p));
    while (st < dr)
    {
        nod = cd[++st];
        for (i=0; i<sz(lv[nod]); ++i)
            if (cap[nod][lv[nod][i]] > 0)
                if (d[nod] + c[nod][lv[nod][i]] < d[lv[nod][i]])
                {
                    d[lv[nod][i]] = d[nod] + c[nod][lv[nod][i]];
                    cd[++dr] = lv[nod][i];
                    p[lv[nod][i]] = nod;
                }
    }
    if (d[2*n+1] < 100000000)
        return 1;
    else
        return 0;
}

double flux(double dist)
{
    int i, j, nod;
    double ret = 0;
    memset(c, 0, sizeof(c));
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
        {
            c[i][j+n] = dst(i,j);
            c[j+n][i] = - c[i][j+n];
        }
    for (i=1; i<=n; ++i)
    {
        lv[i].clear();
        lv[0].pb(i);
        cap[0][i] = 1;
        for (j=1; j<=n; ++j)
            if (c[i][j+n] <= dist)
            {
                lv[i].pb(j+n);
                cap[i][j+n] = 1;
                lv[j+n].pb(i);
            }
        lv[i+n].pb(2*n+1);
        cap[i+n][2*n+1] = 1;
    }
    /*
    while (bellman_ford())
    {
        ret += d[2*n+1];
        for (nod = 2*n+1; p[nod] != -1; nod = p[nod])
        {
            --cap[p[nod]][nod];
            ++cap[nod][p[nod]];
        }
    }*/
    return ret;
}

void solve()
{
    int st, dr, mij, i, j, sol = 0;
    double cost;
    st = 1;
    dr = 0;
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            c[i][j] = dist[++dr] = dst(i, j);
    sort(dist+1, dist+dr+1);
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (merge(dist[mij]))
        {
            sol = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    cost = flux(dist[sol]);
    printf("%.5lf %.5lf\n", dist[sol], cost);
}

int main()
{
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);
    citire();
    solve();
    return 0;
}