Cod sursa(job #1164330)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 1 aprilie 2014 23:45:44
Problema Adapost Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

const int Nmax = 404;
const double inf = 1e9;
const double EPS = 1e-5;

struct NODE
{
    int nod;
    double dist;

    NODE( const int a = 0, const double b = 0 ) : nod( a ), dist( b ) {}

    bool operator < ( const NODE &X ) const
    {
        return dist > X.dist;
    }
};

#define Point pair<double,double>
#define x first
#define y second

vector <int> GG[Nmax];
vector <int> G[2 * Nmax];
priority_queue <NODE> MinHeap;
int C[2 * Nmax][2 * Nmax];
int F[2 * Nmax][2 * Nmax];
double Cost[2 * Nmax][2 * Nmax];
Point soldier[Nmax], shelter[Nmax];
double D[Nmax][Nmax];
int use[Nmax], st[Nmax], dr[Nmax];
int tata[2 * Nmax], coada[2 * Nmax], in_q[2 * Nmax];
double dist[2 * Nmax];

int N;
int source, sink, DIM;

double sq( double a )
{
    return a * a;
}

double euclid_dist( Point A, Point B )
{
    return sqrt( sq( A.x - B.x ) + sq( A.y - B.y ) );
}

void erase_graph()
{
    for ( int i = 1; i <= N; ++i )
            GG[i].clear();

    memset( use, 0, sizeof ( use ) );
    memset( st, 0, sizeof( st ) );
    memset( dr, 0, sizeof( dr ) );
}

void make_graph( double x )
{
    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    if ( D[i][j] <= x )
                            GG[i].push_back( j );
}

int pairup( int nod )
{
    if ( use[nod] )
            return 0;

    use[nod] = 1;

    for ( auto x: GG[nod] )
            if ( !dr[x] )
            {
                st[nod] = x;
                dr[x] = nod;
                return 1;
            }

    for ( auto x: GG[nod] )
            if ( pairup( dr[x] ) )
            {
                st[nod] = x;
                dr[x] = nod;
                return 1;
            }

    return 0;
}

int HopcroftKarp()
{
    for ( int change = 1; change; )
    {
        change = 0;
        memset( use, 0, sizeof( use ) );

        for ( int i = 1; i <= N; ++i )
                if ( !st[i] )
                        change |= pairup( i );
    }

    int match = 0;

    for ( int i = 1; i <= N; ++i )
            match += ( st[i] > 0 );

    return match;
}

int valid( double x )
{
    erase_graph();
    make_graph( x );

    return ( HopcroftKarp() == N );
}

double bsearch()
{
    double st = 0.0f, dr = 2000, m, gasit = -1;

    while ( dr - st > EPS )
    {
        m = ( st + dr ) / 2.0;

        if ( valid( m ) )
        {
            gasit = m;
            dr = m;
        }
        else
        {
            st = m;
        }
    }

    return gasit;
}

void add_edge( int x, int y, int cap, double cost )
{
    G[x].push_back( y );
    G[y].push_back( x );

    C[x][y] = cap;
    Cost[x][y] = +cost;
    Cost[y][x] = -cost;
}

void build_network( double x )
{
    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    if ( D[i][j] <= x )
                    {
                        add_edge( i, j + N, 1, D[i][j] );
                    }

    source = 0;
    sink = 2 * N + 1;
    DIM = 2 * N + 1;

    for ( int i = 1; i <= N; ++i )
            add_edge( source, i, 1, 0 );

    for ( int i = 1; i <= N; ++i )
            add_edge( i + N, sink, 1, 0 );
}

void BellmanFord( int S, int D )
{
    for ( int i = 0; i <= DIM; ++i )
    {
        dist[i] = inf;
        in_q[i] = 0;
    }

    int st, dr;
    coada[st = dr = 1] = S;
    in_q[S] = 1;
    dist[S] = 0;

    while ( st <= dr )
    {
        int nod = coada[ st++ ];

        for ( auto x: G[nod] )
        {
            if ( dist[x] > dist[nod] + Cost[nod][x] && C[nod][x] > F[nod][x] )
            {
                dist[x] = dist[nod] + Cost[nod][x];

                if ( !in_q[x] )
                {
                    in_q[x] = 1;
                    coada[ ++dr ] = x;
                }
            }
        }
    }
}

void init( int S, int D )
{
    for ( int i = 0; i <= DIM; ++i )
    {
        for ( auto x: G[i] )
        {
            if ( dist[i] != inf && dist[x] != inf )
            {
                Cost[i][x] += dist[i] - dist[x];
            }
        }
    }

    for ( int i = 0; i <= DIM; ++i )
    {
        dist[i] = inf;
        tata[i] = 0;
    }

    dist[S] = 0;
}

int Dijkstra( int S, int D )
{
    init( S, D );

    MinHeap.push( NODE( S, 0 ) );

    while ( MinHeap.size() )
    {
        int nod = MinHeap.top().nod;
        double ddd = MinHeap.top().dist;

        MinHeap.pop();

        if ( dist[nod] != ddd ) continue;

        for ( auto x: G[nod] )
        {
            if ( dist[x] > dist[nod] + Cost[nod][x] && C[nod][x] > F[nod][x] )
            {
                dist[x] = dist[nod] + Cost[nod][x];
                tata[x] = nod;
                MinHeap.push( NODE( x, dist[x] ) );
            }
        }
    }

    return ( dist[D] < inf );
}

double EdmondsKarp( int S, int D )
{
    int flow = 0, fmin;
    double flowCost = 0, distD = dist[D];

    while ( Dijkstra( S, D ) )
    {
        fmin = inf;

        for ( int nod = D; nod != S; nod = tata[nod] )
                fmin = min( fmin, C[ tata[nod] ][nod] - F[ tata[nod] ][nod] );

        for ( int nod = D; nod != S; nod = tata[nod] )
        {
            F[ tata[nod] ][nod] += fmin;
            F[nod][ tata[nod] ] -= fmin;
        }

        flow += fmin;
        distD += dist[D];
        flowCost += 1.0 * distD * fmin;
    }


    return flowCost;
}

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

    f >> N;

    for ( int i = 1; i <= N; ++i )
            f >> soldier[i].x >> soldier[i].y;

    for ( int i = 1; i <= N; ++i )
            f >> shelter[i].x >> shelter[i].y;

    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    D[i][j] = euclid_dist( soldier[i], shelter[j] );

    double sol = bsearch();

    build_network( sol );
    BellmanFord( source, sink );

    g << fixed << setprecision( 3 );
    g << sol << " " << EdmondsKarp( source, sink ) << "\n";

    return 0;
}